C ++中的括号扩展

假设我们有一个表示单词列表的字符串S。这里单词中的每个字母都有1个或多个选项。如果只有一个选项，则按原样显示字母。如果有多个选项，则用花括号分隔选项。因此，例如，“ {{a，b，c}””将代表选项[“ a”，“ b”，“ c”]。现在，例如，如果输入像“ {a，b，c} d {e，f}”，则它将表示列表[“ ade”，“ adf”，“ bde”，“ bdf”，“ cde”， “ cdf”]。

以字典顺序返回以这种方式可以形成的所有单词。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个称为ret的数组，定义一个整数类型变量n

• 定义一个方法solve()，它将采用索引，列表和curr作为输入

• 如果index = n，则将curr插入ret并返回

• 对于我来说，范围是0到列表的大小[索引]

• 调用solve（index + 1，list，curr + list [index，i]）

• 在主要方法中，执行以下操作

• 创建一个大小为100的列表，设置n：= 0，标志：= false

• 当我的范围是0到s的大小– 1

• 如果s [i]是逗号，则跳到下一个迭代

• 否则，当s [i]打开大括号时，则设置标志：= true

• 否则，当s [i]关闭大括号时，则将标志：= false设置为n并增加1

• 否则将list [n]增加s [i]，现在如果flag为false，则将n增加1

• 调用resolve（0，list，空字符串）

• 排序ret数组

• 返回ret

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector <string> ret;
   int n;
   vector<string> expand(string s) {
      vector <string> list(100);
      n = 0;
      int flag = false;
      for(int i = 0; i < s.size(); i++){
         if(s[i] == ','){
            continue;
         }else if(s[i] == '{'){
            flag = true;
         }else if(s[i] == '}'){
            flag = false;
            n++;
         }else{
            list[n] += s[i];
            if(!flag)n++;
         }
      }
      solve(0, list);
      sort(ret.begin(), ret.end());
      return ret;
   }
   void solve(int idx, vector <string> list, string curr = ""){
      if(idx == n){
         ret.push_back(curr);
         return;
      }
      for(int i = 0; i < list[idx].size(); i++){
         solve(idx + 1, list, curr + list[idx][i]);
      }
   }
};
main(){
   Solution ob;
   print_vector(ob.expand("{a,b}c{d,e}f"));
}

输入值

"{a,b}c{d,e}f"

输出结果

[acdf, acef, bcdf, bcef, ]