Pythonで辞書を指定してターゲット文字列を形成する方法をいくつか見つけるプログラム

単語と呼ばれる文字列のリストがあり、すべての要素が同じ長さであるとします。 targetという文字列もあります。次のルールの下で、指定された単語を使用してターゲットを生成する必要があります-

• ターゲットは左から右に生成する必要があります。

• target[i]がwords[j] [k]と同じ場合、targetのi番目の文字（0インデックス）を取得するために、単語内のj番目の文字列のk番目の文字を選択できます。

• j番目の単語文字列のk番目の文字を使用すると、x<=k。

  の単語ではどの文字列のx番目の文字も使用できなくなります。

• ターゲット文字列全体が形成されるまで、これらのプロセスを繰り返します。

したがって、単語からターゲットを取得する方法をいくつか見つける必要があります。答えは非常に大きい可能性があるため、10 ^ 9+7を法として答えを返します。

したがって、入力がwords =["pqqp"、 "qppq"]、target ="qpq"の場合、出力は4になります。

• "qpq"->インデックス0（ "qppq"）、インデックス1（ "qppq"）、インデックス2（ "pqqp"）

• "qpq"->インデックス0（ "qppq"）、インデックス1（ "qppq"）、インデックス3（ "qppq"）

• "qpq"->インデックス0（ "qppq"）、インデックス2（ "qppq"）、インデックス3（ "qppq"）

• "qpq"->インデックス1（ "pqqp"）、インデックス2（ "qppq"）、インデックス3（ "qppq"）

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

• m：=単語数、

• n：=ターゲットのサイズ

• d：=m個の異なる空のマップで満たされたサイズmのリスト

• 単語のwごとに、実行します

  • wの各インデックスjと単語cについて、実行します

    • d [j、c]：=d [j、c] + 1

• 関数dfs（）を定義します。これにはi、jが必要です

• iがnと同じ場合、

  • 1を返す

• iがmと同じ場合、

  • 0を返す

• return（dfs（i、j + 1）+ dfs（i + 1、j + 1）* d [j、target [i]]）mod（10 ^ 9 + 7）

• メインメソッドからdfs（0、0）を返します

例

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

from collections import Counter
def solve(words, target):
   m, n = len(words[0]), len(target)
   d = [Counter() for _ in range(m)]
   for w in words:
      for j, c in enumerate(w):
         d[j][c] += 1

   def dfs(i, j):
      if i == n:
         return 1
      if j == m:
         return 0
      return (dfs(i, j+1) + dfs(i+1, j+1) * d[j][target[i]]) % int(1e9 + 7)

   return dfs(0, 0)

words = ["pqqp","qppq"]
target = "qpq"
print(solve(words, target))

入力

"95643", "45963"

出力

4