leetcode 1087 - Brace Expansion

https://leetcode.com/problems/brace-expansion/

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
class Solution {
public:
vector<string> all_result;

vector<string> expand(string S) {
string result;
recursive(S, result, 0);
sort(all_result.begin(), all_result.end());

return all_result;
}

void recursive(string &S, string &result, int i) {
if (i == S.size()) {
all_result.push_back(result);
return;
}

if (S[i] == '{') {
string tmp;

i++;
while (S[i] != '}') {
if (S[i] != ',')
tmp.push_back(S[i]);
i++;
}

i++;
for (char c : tmp) {
result.push_back(c);
recursive(S, result, i);
result.pop_back();
}
} else {
result.push_back(S[i]);
recursive(S, result, i+1);
result.pop_back();
}
}
};