C++中的花括号展开

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

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

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

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

  • 定义一个名为solve()的方法，它将index、list和curr作为输入

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

  • 对于范围为0到list[index]大小的i

    • 调用solve(index + 1, list, curr + list[index, i])

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

  • 创建一个大小为100的列表，设置n := 0，flag := false

  • 对于范围为0到s大小减1的i

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

    • 否则，当s[i]是开括号时，设置flag := true

    • 否则，当s[i]是闭括号时，设置flag := false并将n加1

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

  • 调用solve(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, ]

更新于：2020年4月30日

267 次浏览

启动您的职业生涯

完成课程获得认证

开始
广告