C++でのブレース拡張

単語のリストを表す文字列Sがあるとします。ここで、単語の各文字には1つ以上のオプションがあります。オプションが1つしかない場合、文字はそのまま表示されます。複数のオプションがある場合は、中括弧でオプションを区切ります。したがって、たとえば、「{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、フラグ：=falseを設定します

• 0からsのサイズまでの範囲のiの場合– 1

  • s [i]がコンマの場合、次の反復にスキップします

  • それ以外の場合、s [i]が中括弧を開いているときに、フラグを設定します：=true

  • それ以外の場合、s [i]が中括弧を閉じるときは、フラグ：=falseを設定し、nを1増やします

  • それ以外の場合は、list[n]をs[i]増やします。ここで、フラグがfalseの場合は、nを1増やします

    。

• 呼び出しsolve（0、リスト、空の文字列）

• 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, ]