Pythonで選択してすべての可能な文字列を生成するプログラム

小文字のアルファベット文字、「[」、「|」、「]」などの他の文字の文字列があるとします。ここで、「[a | b | c]」は、「a」、「b」、または「c」のいずれかを可能性として選択できることを示します。 sが表すことができるすべての可能な値を含む文字列のリストを見つける必要があります。ここで、「[]」はネストできず、任意の数の選択肢があります。

したがって、入力がs ="[d | t | l] im [e | s]"の場合、出力は['dime'、'dims'、'lime'、'lims'、'time'になります。 、'tims']

これを解決するには、次の手順に従います。

• sが空の場合、
  • 空白の文字列を含むリストを返す
• n：=sのサイズ
• seq：=新しいリスト、res：=新しいリスト
• 関数helper（）を定義します。これには可能性があります
  • posがnと同じ場合、
    • seqに存在する各要素を結合し、resに挿入します
  • それ以外の場合、
    • s[インデックス位置から終了まで]の部分文字列に「[」がある場合
      • start：=pos +s[インデックス位置から終了まで]のサブストリング内の「[」のインデックス
      • end：=pos +s[インデックス位置から終了まで]のサブストリング内の"]"のインデックス
      • sの部分文字列の最初から最後までを「|」で割ったオプションごとに、
        を実行します。
        • シーケンスの最後にs[インデックス位置から開始-1]を挿入します
        • シーケンスの最後にオプションを挿入
        • helper（end + 1）
        • seqから最後の2つの要素を削除します
  • それ以外の場合、
    • seqの最後にs[インデックス位置から終了まで]を挿入します
    • helper（n）
    • seqから最後の要素を削除する
• メインの方法から次の手順を実行します。
• helper（0）
• 解像度を並べ替えて返す

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

例

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']