C++で実装するブレース展開アルゴリズム

文字列 S が単語のリストを表していると考えます。ここで、単語を構成する各文字には1つ以上の選択肢（オプション）が存在します。選択肢が1つだけの場合、その文字はそのまま記述されます。一方、複数の選択肢がある場合には、波括弧 { } によって選択肢が囲まれます。

たとえば、「{a,b,c}」という記述は選択肢「a」「b」「c」を表します。入力が「{a,b,c}d{e,f}」のような形式で与えられた場合、これは次の6つの単語からなるリストを意味します。

[ade, adf, bde, bdf, cde, cdf]

本記事では、このような形式の文字列から生成可能なすべての単語を列挙し、辞書順（lexicographical order）に並べて返すアルゴリズムをC++で実装する方法を解説します。

解法のアプローチ

この問題はバックトラッキング（深さ優先探索）を用いることで効率的に解くことができます。まず入力文字列を解析して「選択肢のグループ」ごとのリストを作成し、その後すべての組み合わせを再帰的に生成します。全体の流れは以下の通りです。

• 結果を格納する配列 ret と、グループ数を数える整数型変数 n を定義します。

• 再帰メソッド solve() を定義します。引数としてインデックス、リスト、現在構築中の文字列 curr を受け取ります。

• index が n に達したら、1つの単語が完成したことを意味するため、curr を ret に挿入して処理を終了します。

• i を 0 から list[index] のサイズ未満まで繰り返し、solve(index + 1, list, curr + list[index][i]) を再帰的に呼び出します。

メインメソッドでの解析手順

• サイズ100の文字列ベクトル list を作成し、n := 0、flag := false で初期化します。

• i を 0 から s.size() - 1 まで繰り返しながら、各文字に対して以下の判定を行います。

  • s[i] がカンマ「,」の場合：区切り文字なので何もせず次の反復へ進みます。

  • s[i] が開き波括弧「{」の場合：flag := true に設定し、以降の文字を選択肢として収集します。

  • s[i] が閉じ波括弧「}」の場合：flag := false に設定し、グループが完了したので n を1増やします。

  • 上記以外の場合：list[n] に s[i] を追加します。flag が false のときは単独の文字として扱うため n を1増やします。

• solve(0, list, "") を呼び出して全組み合わせを生成します。

• ret 配列をソートし、結果を返します。

C++での実装例

それでは、実際のコードを見てみましょう。

#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;
      bool 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]);
      }
   }
};
int main(){
   Solution ob;
   print_vector(ob.expand("{a,b}c{d,e}f"));
   return 0;
}

入力

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

出力

[acdf, acef, bcdf, bcef]

この例では、最初のグループ「{a,b}」と2番目のグループ「{d,e}」の組み合わせにより、4つの単語 acdf、acef、bcdf、bcef が生成され、辞書順に出力されています。

計算量の目安

解析フェーズは入力文字列の長さに対して線形時間 O(|S|) で完了します。組み合わせ生成のフェーズでは、各グループの選択肢数の積 P 個の単語が生成されるため、最終的なソートを含めた全体の時間計算量は O(P log P) 程度となります。選択肢の数が多い入力では組み合わせが指数的に増える点に注意してください。