Pythonで選択パターンから生成可能なすべての文字列を求めるプログラム

問題の概要

小文字のアルファベットと、「[」「|」「]」といった特殊文字で構成された文字列 s が与えられるとします。ここで「[a|b|c]」という表記は、「a」「b」「c」のいずれか1つを選択できることを意味します。このとき、文字列 s が表現しうるすべての値を含むリストを作成する必要があります。なお、「[]」の入れ子（ネスト）は禁止されており、選択肢の数は任意とします。

例えば、入力が s = "[d|t|l]im[e|s]" の場合、出力は次のようになります。

['dime', 'dims', 'lime', 'lims', 'time', 'tims']

解決のための手順

この問題は、再帰的なバックトラッキング（深さ優先探索）を用いて解きます。具体的には、以下の手順に従います。

• 文字列 s が空の場合、空文字列を1つだけ含むリストを返します。
• n := 文字列 s の長さとします。
• seq := 新しいリスト（構築中の文字列断片を保持）、res := 新しいリスト（結果を保持）を用意します。
• 引数 pos を取る関数 helper() を定義します。
  • pos が n と等しい場合：seq 内の各要素を連結し、res に追加します。
  • それ以外の場合：
    • s[pos:]（pos 以降の部分文字列）に「[」が含まれる場合：
      • start := pos ＋ s[pos:] 内での「[」のインデックス
      • end := pos ＋ s[pos:] 内での「]」のインデックス
      • s[start+1:end] を「|」で分割した各 option について、次を繰り返します。
        • seq の末尾に s[pos:start] を追加
        • seq の末尾に option を追加
        • helper(end + 1) を呼び出す
        • seq から最後の2要素を削除（バックトラック）
    • それ以外の場合：
      • seq の末尾に s[pos:] を追加
      • helper(n) を呼び出す
      • seq から最後の要素を削除
• メイン処理では、helper(0) を呼び出し、res をソートして返します。

実装例

より理解を深めるために、以下の実装を見てみましょう。

class Solution:
   def solve(self, s):
      if not s:
         return [""]
      n = len(s)

      def helper(pos):
         if pos == n:
            res.append("".join(seq))
         else:
            if "[" in s[pos:]:
               start = pos + s[pos:].index("[")
               end = pos + s[pos:].index("]")
               for option in s[start + 1 : end].split("|"):
                  seq.append(s[pos:start])
                  seq.append(option)
                  helper(end + 1)
                  seq.pop()
                  seq.pop()
            else:
               seq.append(s[pos:])
               helper(n)
               seq.pop()

      seq = []
      res = []
      helper(0)
      return sorted(res)

ob = Solution()
s = "[d|t|l]im[e|s]"
print(ob.solve(s))

入力

"[d|t|l]im[e|s]"

出力

['dime', 'dims', 'lime', 'lims', 'time', 'tims']

アルゴリズムのポイント

このアルゴリズムの核心は、バックトラッキングによる全探索です。「[」が見つかるたびに、その中の各選択肢に対して再帰的に分岐することで、すべての組み合わせを網羅的に生成できます。リスト seq への追加と削除（pop）を繰り返すことで、状態をメモリ効率よく管理している点も特徴です。また、最後に sorted() を適用することで、結果が辞書順に整列され、読みやすい出力となります。計算量は、選択グループごとの候補数を掛け合わせた組み合わせ総数に比例して増加するため、選択肢が多い場合は出力件数が急増することに注意してください。