1087. Brace Expansion
You are given a string s representing a list of words. Each letter in the word has one or more options.
- If there is one option, the letter is represented as is.
- If there is more than one option, then curly braces delimit the options. For example, “{a,b,c}” represents options [“a”, “b”, “c”].
For example, if s = “a{b,c}”, the first character is always ‘a’, but the second character can be ‘b’ or ‘c’. The original list is [“ab”, “ac”].
Return all words that can be formed in this manner, sorted in lexicographical order.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
vector<vector<string>> candidate;
vector<string> res;
vector<string> parse(string& s, int &i) {
vector<string> res;
string tmp ="";
while(i < s.length() and s[i] != '}') {
if(s[i] == ',') {
res.push_back(tmp);
tmp = "";
} else {
tmp += s[i];
}
i++;
}
if(tmp != "") res.push_back(tmp);
sort(res.begin(), res.end());
return res;
}
void backTracking(int i, string s) {
if(i == candidate.size()) {
res.push_back(s);
return;
}
for(auto str : candidate[i]) {
backTracking(i + 1, s + str);
}
}
public:
vector<string> expand(string s) {
string tmp="";
for(int i = 0; i < s.length(); i++) {
if(s[i] == '{') {
if(tmp.length() > 0) candidate.push_back({tmp});
candidate.push_back(parse(s,++i));
tmp = "";
} else tmp += s[i];
}
if(tmp.length() > 0) candidate.push_back({tmp});
tmp = "";
backTracking(0,tmp);
return res;
}
};
|
