生成全部可能的字符串

原题：
input a string: a{b,c}{d,e} ，return a list of string [abd, abe, acd, ace]

followup是如果有嵌套怎么办：
a{b,c{d,e}}

在地里看到几次了。如果没有嵌套，直接用backtracking就可以。但是有嵌套的话该怎么办？都不知道followup该生成什么..

可以先理解{b,c{d,e}}能生成什么？根据观察到的规则，{b, cd, ce}

那么，a{b, cd, ce}能生成什么？ab, acd, ace

比起理解输出是什么 我觉得parse这个嵌套的string比较麻烦

能写码就不bb 写了一个有点繁琐的

1. class ExpandString {
   
2. public:
   
3.   vector<string> tokenize(string & str) {
   
4.     cout << "TOK: " << str << endl;
   
5.     vector<string> tokens;
   
6.     str.push_back(',');
   
7.     int start = 0;
   
8.     for (int i = 0; i < str.size(); ++i) {
   
9.       if (isalpha(str[i])) {
   
10.         continue;
    
11.       } else if (str[i] == '{') {
    
12.         int cnt = 0;
    
13.         while (true) {
    
14.           if (str[i] == '{') {
    
15.             ++cnt;
    
16.           } else if (str[i] == '}') {
    
17.             --cnt;
    
18.           }
    
19.           if (cnt == 0) {
    
20.             break;
    
21.           }
    
22.           ++i;
    
23.         }
    
24.       } else if (str[i] == ',') {
    
25.         string w = str.substr(start, i - start);
    
26.         start = i + 1;
    
27.         vector<string> res = expand(w);
    
28.         copy(res.begin(), res.end(), back_inserter(tokens));
    
29.       }
    
30.     }
    
31.     return tokens;
    
32.   }
    
33.   vector<string> expand(string & str) {
    
34.     cout << "EXP: " << str << endl;
    
35.     auto loc = str.find('{');
    
36.     if (loc == string::npos) {
    
37.       return {str};
    
38.     }
    
39. 
    
40.     vector<string> out = {""};
    
41. 
    
42.     for (int i = 0; i < str.size(); ++i) {
    
43.       if (isalpha(str[i])) {
    
44.         int e = i;
    
45.         while (e < str.size() && isalpha(str[e])) {
    
46.           ++e;
    
47.         }
    
48.         string w = str.substr(i, e - i);
    
49.         for (int j = 0; j < out.size(); ++j) {
    
50.           out[j] = out[j] + w;
    
51.         }
    
52.         i = e - 1;
    
53.       } else {
    
54.         // bracket
    
55.         int cnt = 0;
    
56.         int e = i;
    
57.         while (true) {
    
58.           if (str[e] == '{') {
    
59.             ++cnt;
    
60.           } else if (str[e] == '}') {
    
61.             --cnt;
    
62.           }
    
63.           if (cnt == 0) {
    
64.             break;
    
65.           }
    
66.           ++e;
    
67.         }
    
68.         string w = str.substr(i + 1, e - i - 1);
    
69.         vector<string> ws = tokenize(w);
    
70.         vector<string> base;
    
71.         base.swap(out);
    
72.         for (auto & s1: base) {
    
73.           for (auto & s2: ws) {
    
74.             out.push_back(s1 + s2);
    
75.           }
    
76.         }
    
77.         i = e;
    
78.       }
    
79.     }
    
80.     return out;
    
81.   }
    
82. };
    

复制代码

Test Case

1. int main() {
   
2.   string input = "{x,y}a{b,c,e{d,f}}";
   
3.   ExpandString es;
   
4.   vector<string> result = es.expand(input);
   
5.   for (auto s: result) {
   
6.     cout << s << " ";
   
7.   }
   
8.   cout << endl;
   
9. }
   

复制代码

OUTPUT:

1. EXP: {x,y}a{b,c,e{d,f}}
   
2. TOK: x,y
   
3. EXP: x
   
4. EXP: y
   
5. TOK: b,c,e{d,f}
   
6. EXP: b
   
7. EXP: c
   
8. EXP: e{d,f}
   
9. TOK: d,f
   
10. EXP: d
    
11. EXP: f
    
12. xab xac xaed xaef yab yac yaed yaef
    

复制代码