Brace Expansion
Medium · Graphs · Explanation and code example
Backtracking
How it works
Backtracking is a natural fit for generating all combinations. First, we parse the input string to extract all options for each position. Then we build words character by character: at each position, we try each available option, add it to the current word, recurse to the next position, and then remove it (backtrack) to try the next option.
Steps
- Parse the input string to create a list of options for each position:
- For each segment, extract either a single character or sorted characters from braces.
- Define a recursive backtracking function:
- Base case: if the current string length equals the number of positions, add it to the result.
- Get the options for the current position.
- For each option:
- Append the character to the current string.
- Recurse to fill the next position.
- Remove the last character (backtrack).
- Call the backtracking function with an empty string and return the result.
Complexity
-
Time complexity:
O(N × 3^{N/7}) -
Space complexity:
O(N)
Where
Nis the length of the given string.
Things to watch for
Forgetting to Sort Options Within Braces
The problem requires the output to be in lexicographically sorted order. Options within braces like {b,a,c} must be sorted to [a,b,c] before generating combinations, otherwise the final result will be out of order.
Incorrect Index Advancement After Closing Brace
When parsing a brace group, after finding }, you must advance the index past the } character. Off-by-one errors here cause infinite loops or skipped characters.
Not Handling Single Characters Outside Braces
Single characters outside braces (like a in a{b,c}) should be treated as a group with one option. Forgetting this case causes the character to be skipped entirely in the output.
Python code example
from typing import List
class Solution:
def expand(self, s: str) -> List[str]:
all_options = []
# Store all options for each position
def store_all_options():
pos = 0
while pos < len(s):
curr_options = []
# If the first character is not '{', it means a single character
if s[pos] != '{':
curr_options.append(s[pos])
else:
# Store all the characters between '{' and '}'
while s[pos] != '}':
if 'a' <= s[pos] <= 'z':
curr_options.append(s[pos])
pos += 1
# Sort the list
curr_options.sort()
all_options.append(curr_options)
pos += 1
def generate_words(curr_string, expanded_words):
# If the currString is complete, we can store and return
if len(curr_string) == len(all_options):
expanded_words.append(''.join(curr_string))
return
# Fetch the options for the current index
curr_options = all_options[len(curr_string)]
# Add the character and go into recursion
for c in curr_options:
curr_string.append(c)
generate_words(curr_string, expanded_words)
# Backtrack to previous state
curr_string.pop()
# Store the character options for different indices
store_all_options()
expanded_words = []
generate_words([], expanded_words)
return expanded_words
C++ code example
class Solution {
public:
vector<vector<char>> allOptions;
void storeAllOptions(string& s) {
for (int pos = 0; pos < s.size(); pos++) {
vector<char> currOptions;
// If the first character is not '{', it means a single character
if (s[pos] != '{') {
currOptions.push_back(s[pos]);
} else {
// Store all the characters between '{' and '}'
while (s[pos] != '}') {
if (s[pos] >= 'a' && s[pos] <= 'z') {
currOptions.push_back(s[pos]);
}
pos++;
}
// Sort the list
sort(currOptions.begin(), currOptions.end());
}
allOptions.push_back(currOptions);
}
}
void generateWords(string currString, vector<string>& expandedWords) {
// If the currString is complete, we can store and return
if (currString.size() == allOptions.size()) {
expandedWords.push_back(currString);
return;
}
// Fetch the options for the current index
vector<char> currOptions = allOptions[currString.size()];
// Add the character and go into recursion
for (char c : currOptions) {
currString += c;
generateWords(currString, expandedWords);
// Backtrack to previous state
currString.pop_back();
}
}
vector<string> expand(string s) {
// Store the character options for different indices
storeAllOptions(s);
vector<string> expandedWords;
generateWords("", expandedWords);
return expandedWords;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.