1087. Brace Expansion


Problem Description

In this problem, we're given a string s that represents a list of words with some embedded choices. These choices are expressed in two different ways:

  • If a letter doesn't have any alternatives, it appears in the string as a normal character.
  • If a letter has multiple options, these options are enclosed within curly braces {}. Each option within the braces is separated by a comma. For example, the string "{a,b,c}" could represent three alternatives: 'a', 'b', or 'c'.

Our task is to expand this string s by generating all possible combinations according to the options given for each character, and return them in a list sorted in lexicographical (dictionary) order.

For instance, given the input s = "a{b,c}", we should return ["ab", "ac"], which are all possible words formed by picking one option at each position where choices are given.

Intuition

To solve this problem, we can approach it with a depth-first search (DFS) strategy. Here's how we can break it down:

  • Parsing the input string: We need to parse the input string s to separate each character or group of options (delimited by {}) into a list. This gives us a clear structure that we can easily iterate over.

  • Building combinations with DFS: We will use DFS to explore every possible combination by trying each option at every step. DFS allows us to dive deep into each branching path of options until we reach the end of the list, at which point we will have a complete word.

  • Backtracking for cleanliness: While we're exploring options with DFS, we need to add and later remove characters from a temporary list that represents the current word being built. This method is known as backtracking and it's a crucial part of the DFS approach since it helps us keep track of the current state without affecting other branches in the search tree.

  • Sorting the results: Finally, once we have found all possible combinations, we'll sort the resulting list to conform to the lexicographical order requirement stated in the problem.

The provided solution code follows these steps using a couple of helper functions convert for parsing the string and dfs for doing the depth-first search and backtracking. The convert function is designed to handle the curly braces and split the options into a list, while the dfs function does the heavy lifting of constructing the result set. Once the DFS traversal is complete, a sorting operation ensures the results are returned in the correct order.

Solution Approach

The solution to the problem involves a depth-first search (DFS) algorithm along with a strategy for parsing the input string and organizing it into a list of options. Below, we'll walk through the implementation of the solution step-by-step:

  1. Parsing the input:

    • The input string s is parsed with the help of the convert function.
    • The function checks each character of the input, looking for the opening curly brace {.
    • When it finds an opening curly brace, it looks for the corresponding closing brace } and extracts the options within as a list after splitting by comma ,.
    • If there are no curly braces found, the characters are appended to a list as a single-item list.
    • The result is stored in items which is a list of lists that represents all the individual units (single characters or groups of options) that can combine to form the required words.
  2. Depth-first search (DFS):

    • We use the dfs function to recursively construct all possible words from the items list.
    • The function dfs takes two arguments, i, which denotes the current position in items we're at, and t, a temporary list that holds the current word being constructed.
    • On each recursive call, the function iterates over all options in items[i], adds an option to t, and recursively calls itself with the next position (i + 1).
    • Base case: If i equals the length of items, it means we've reached the end, and a complete word has been constructed. This word is then joined and added to the final answer list ans.
  3. Backtracking:

    • During the DFS, we keep appending choices to the temporary list t.
    • After exploring each option, we need to revert back to the state before the choice was made. This is achieved by popping the last element from t, allowing us to backtrack and explore the next option.
  4. Sorting and returning the result:

    • After all possible words have been constructed, we sort the list ans to satisfy the lexicographical order requirement.
    • The sorted list is returned as the final output of the expand function.

Here is a snippet of the code from the provided solution that demonstrates the use of DFS and backtracking:

1def dfs(i, t):
2    if i == len(items):
3        ans.append(''.join(t))
4        return
5    for c in items[i]:
6        t.append(c)
7        dfs(i + 1, t)
8        t.pop()

In the code, t.append(c) corresponds to making a choice, the recursive call dfs(i + 1, t) explores deeper with the choice made, and t.pop() undoes the choice (backtracking) so we can explore the next option. The entire solution is a classic application of DFS with backtracking to generate all possible combinations.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's work through a simple example to illustrate the solution approach. We will apply the DFS strategy on the input string s = "k{a,b}{n,m}".

  1. Parsing the input:

    • The convert function scans the string from left to right.
    • It identifies 'k' as a normal character, so it is included as ['k'].
    • The function finds {a,b} and splits the options into a list ['a', 'b'].
    • Then it finds {n,m} and similarly creates the list ['n', 'm'].
    • We end up with items = [['k'], ['a', 'b'], ['n', 'm']].
  2. Depth-first search (DFS):

    • We begin the DFS by calling the function dfs with i = 0 and an empty list t = [].
    • At items[0], we have one option 'k'. We add it to t making it ['k'].
    • We call dfs(i + 1, t) with i = 1. Here, we have two options 'a' and 'b'.
    • First, we choose 'a', update t to ['k', 'a'], and call dfs(i + 1, t) to proceed to the next item.
    • At items[2], we again have two choices 'n' and 'm'.
    • We pick 'n', make t ['k', 'a', 'n'], and reach the base case of our DFS (i == len(items)). We add 'kan' to ans.
    • We backtrack by popping 'n' from t, and now t is back to ['k', 'a'].
    • Next, we pick 'm' and go through a similar process, resulting in 'kam' being added to ans.
    • Backtracking again to ['k'], we return to the choice at items[1] and pick 'b' this time.
    • We repeat the process for 'n' and 'm' with the new prefix 'kb', resulting in 'kbn' and 'kbm' being added to ans.
  3. Backtracking:

    • The backtracking is done after each option is explored. It allows us to remove the last choice and explore other paths.
    • This is seen in the example as we pop the last character of t after exploring options 'n' and 'm'.
  4. Sorting and returning the result:

    • Once all the paths are explored, we have ans = ['kan', 'kam', 'kbn', 'kbm'].
    • We sort ans to get ['kam', 'kan', 'kbm', 'kbn'].
    • The sorted list is the final output, containing all combinations in lexicographical order.

Here's a step-by-step visualization of dfs execution for our example input:

1('k') -> ('ka') -> ('kan') - Add to ans and backtrack
2       -> ('kam') - Add to ans and backtrack to ('k')
3       -> ('kb') -> ('kbn') - Add to ans and backtrack
4       -> ('kbm') - Add to ans and finish

By following the systematic approach of DFS and backtracking, we can efficiently generate all possible combinations for more complicated inputs using the same logic.

Python Solution

1from typing import List
2
3class Solution:
4    def expand(self, s: str) -> List[str]:
5        # A helper function to convert the input string into a list of tokens, 
6        # where each token is either a character or a list of characters.
7        def tokenize(s: str):
8            if not s:
9                return
10            if s[0] == '{':
11                # Find the closing brace and split characters within '{' and '}'.
12                closing_brace_index = s.find('}')
13                tokens.append(s[1:closing_brace_index].split(','))
14                # Continue tokenizing the rest of the string after the '}'.
15                tokenize(s[closing_brace_index + 1:])
16            else:
17                # Find the next opening brace '{' if any.
18                opening_brace_index = s.find('{')
19                if opening_brace_index != -1:
20                    # Add characters before the next '{' as a single token.
21                    tokens.append([s[:opening_brace_index]])
22                    # Continue tokenizing from the '{'.
23                    tokenize(s[opening_brace_index:])
24                else:
25                    # No more braces, add the remaining characters as a single token.
26                    tokens.append([s])
27
28        # A helper function to perform a depth-first search for generating all possible strings.
29        def dfs(index, current_string):
30            if index == len(tokens):
31                # Reached the end of tokens, add the joined string to the answers list.
32                results.append(''.join(current_string))
33                return
34            for character in tokens[index]:
35                # Add current character and continue deeper into the search.
36                current_string.append(character)
37                dfs(index + 1, current_string)
38                # Pop the character to backtrack for the next character.
39                current_string.pop()
40
41        # This list will hold the tokenized version of the string.
42        tokens = []
43        tokenize(s)
44      
45        # List to store the results.
46        results = []
47        # Perform DFS starting with an empty string.
48        dfs(0, [])
49        # Sort the results alphabetically before returning.
50        results.sort()
51        return results
52
53# The following lines could be used to test the solution:
54# sol = Solution()
55# print(sol.expand("{a,b}c{d,e}f"))
56

Java Solution

1import java.util.ArrayList;
2import java.util.Collections;
3import java.util.List;
4
5class Solution {
6    // List to store final combinations.
7    private List<String> combinations;
8  
9    // List of string arrays, where each array represents a part of the input string.
10    private List<String[]> parts;
11
12    // Main function to expand the string.
13    public String[] expand(String s) {
14        combinations = new ArrayList<>();
15        parts = new ArrayList<>();
16      
17        parseInputString(s); // Convert the string into parts.
18        depthFirstSearch(0, new ArrayList<>()); // Build the combinations.
19        Collections.sort(combinations); // Sort the combinations alphabetically.
20      
21        return combinations.toArray(new String[0]); // Return the combinations as an array.
22    }
23
24    // Helper function to convert the string into different parts.
25    private void parseInputString(String s) {
26        while (!s.equals("")) {
27            if (s.charAt(0) == '{') {
28                int endIndex = s.indexOf("}");
29                parts.add(s.substring(1, endIndex).split(","));
30                s = s.substring(endIndex + 1);
31            } else {
32                int endIndex = s.indexOf("{");
33                if (endIndex != -1) {
34                    parts.add(new String[]{s.substring(0, endIndex)});
35                    s = s.substring(endIndex);
36                } else {
37                    parts.add(new String[]{s}); 
38                    break;
39                }
40            }
41        }
42    }
43
44    // Helper function to perform depth-first search to build the combinations.
45    private void depthFirstSearch(int index, List<String> current) {
46        if (index == parts.size()) {
47            combinations.add(String.join("", current));
48            return;
49        }
50        for (String str : parts.get(index)) {
51            current.add(str);
52            depthFirstSearch(index + 1, current);
53            current.remove(current.size() - 1); // Backtrack
54        }
55    }
56}
57

C++ Solution

1#include <vector>
2#include <string>
3#include <algorithm>
4
5class Solution {
6public:
7    std::vector<std::string> combinations; // Vector to store final combinations.
8    std::vector<std::vector<std::string>> parts; // Vector of vector of strings, each representing a part of the input string.
9
10    // Main function to expand the string.
11    std::vector<std::string> expand(std::string s) {
12        parseInputString(s); // Convert the string into parts.
13        depthFirstSearch(0, ""); // Build the combinations.
14        std::sort(combinations.begin(), combinations.end()); // Sort the combinations alphabetically.
15
16        return combinations; // Return the combinations as a vector.
17    }
18
19private:
20    // Helper function to convert the string into different parts.
21    void parseInputString(const std::string& s) {
22        std::string str = s; // Working copy of the input string
23        while (!str.empty()) {
24            if (str[0] == '{') {
25                size_t endIndex = str.find("}");
26                parts.push_back(split(str.substr(1, endIndex - 1), ',')); // Exclude '{' and '}'
27                str = str.substr(endIndex + 1);
28            } else {
29                size_t endIndex = str.find("{");
30                if (endIndex != std::string::npos) {
31                    parts.push_back(std::vector<std::string>{str.substr(0, endIndex)});
32                    str = str.substr(endIndex);
33                } else {
34                    parts.push_back(std::vector<std::string>{str});
35                    break;
36                }
37            }
38        }
39    }
40
41    // Helper function to split a string by a delimiter and return a vector of strings.
42    std::vector<std::string> split(const std::string& s, char delimiter) {
43        std::vector<std::string> tokens;
44        std::string token;
45        std::istringstream tokenStream(s);
46        while (std::getline(tokenStream, token, delimiter)) {
47            tokens.push_back(token);
48        }
49        return tokens;
50    }
51
52    // Helper function to perform depth-first search to build the combinations.
53    void depthFirstSearch(int index, std::string current) {
54        if (index == parts.size()) {
55            combinations.push_back(current);
56            return;
57        }
58        for (const std::string& str : parts[index]) {
59            depthFirstSearch(index + 1, current + str); // Combine current string with the new part and recurse
60        }
61    }
62};
63

Typescript Solution

1// Type definitions for consistency.
2type Part = string[];
3type Combination = string[];
4
5// Variable to store the final combinations.
6let combinations: Combination[] = [];
7
8// Variable to store the parts of the input string.
9let parts: Part[] = [];
10
11// Function to expand the string.
12function expand(s: string): string[] {
13    combinations = [];
14    parts = [];
15
16    // Convert the string into parts.
17    parseInputString(s);
18    // Build the combinations using depth-first search.
19    depthFirstSearch(0, []);
20
21    // Sort the combinations alphabetically.
22    const sortedCombinations: string[] = combinations.sort();
23
24    // Return the combinations as an array.
25    return sortedCombinations;
26}
27
28// Helper function to convert the input string into different parts.
29function parseInputString(s: string): void {
30    let remaining: string = s;
31
32    while (remaining !== "") {
33        if (remaining.charAt(0) === '{') {
34            const endIndex: number = remaining.indexOf("}");
35            parts.push(remaining.substring(1, endIndex).split(","));
36            remaining = remaining.substring(endIndex + 1);
37        } else {
38            const endIndex: number = remaining.indexOf("{");
39            if (endIndex !== -1) {
40                parts.push([remaining.substring(0, endIndex)]);
41                remaining = remaining.substring(endIndex);
42            } else {
43                parts.push([remaining]);
44                break;
45            }
46        }
47    }
48}
49
50// Helper function to perform depth-first search and build the combinations.
51function depthFirstSearch(index: number, current: Combination): void {
52    if (index === parts.length) {
53        combinations.push(current.join(""));
54        return;
55    }
56    for (let str of parts[index]) {
57        current.push(str);
58        depthFirstSearch(index + 1, current);
59        current.pop(); // Backtrack
60    }
61}
62

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by the convert and the dfs functions.

The convert function is a recursive function that processes the string s. In the worst case, it will process each character of s once, giving us a time complexity of O(N) where N is the length of the input string s.

The dfs (Depth-First Search) function is called for each of the paths that can be created from the input string. In the worst case, if each character of the input string s is inside brackets {...} and has k options, the depth of the recursion will be N, and each level will branch out k times leading to a total of k^N possibilities. Hence, the worst-case time complexity for this recursive function is O(k^N).

Therefore, the combined worst-case time complexity for both functions becomes O(N + k^N) where N is the length of the input string s and k is the maximum number of options inside any set of curly brackets.

Space Complexity

The space complexity is largely determined by the items list and the space required by the recursive dfs function call stack.

The items list holds the options that are generated by processing the input string s. In the worst case, if each character is a separate option, it will have N elements each with at most k options, leading to a space complexity of O(N * k).

The dfs function will have a call stack depth of at most N (length of the input string s), and on each level, it will have a list t growing up to size N. This gives us an additional space complexity of O(N^2) which accounts for the stack frames and the temporary list used in each call.

Combining the space complexities for the items list and the call stack of dfs, we have a total worst-case space complexity of O(N*k + N^2). Simplifying this, and considering that k could be equal to N in the worst case, we obtain a final worst-case space complexity of O(N^2).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫