Pythonで辞書(文字列リスト)からターゲット文字列を形成する方法の数を求めるプログラム

問題の概要

すべて同じ長さの文字列で構成されるリスト words と、文字列 target が与えられます。次のルールに従い、words を使って target を生成することを考えます。

• target は左から右へ順に構築します。
• target の i 番目(0始まり)の文字を得るには、target[i] が words[j][k](words の j 番目の文字列の k 番目の文字)と一致するとき、その文字を選択できます。
• ある文字列の k 番目の文字を一度使用すると、それ以降はどの文字列でも x ≤ k を満たす x 番目の文字は使用できません。
• この手順を target 全体が完成するまで繰り返します。

ここで求めたいのは、words から target を作る方法の総数です。答えは非常に大きな値になる可能性があるため、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")

解き方のアプローチ

この問題は深さ優先探索(DFS)を用いて解くことができます。大まかな流れは以下の通りです。

• m := 各文字列の長さ(len(words[0]))
• n := target の長さ
• d := サイズ m のリストで、各要素は空の Counter(辞書)。位置ごとに各文字が何個含まれるかを記録します。
• words の各文字列 w に対して、その各インデックス j と文字 c について d[j][c] += 1 を実行します。
• 関数 dfs(i, j) を定義します。
  • i == n の場合(target をすべて作り終えた場合)は 1 を返す。
  • j == m の場合(利用できる文字の位置が尽きた場合)は 0 を返す。
  • それ以外の場合は (dfs(i, j+1) + dfs(i+1, j+1) * d[j][target[i]]) mod (10^9 + 7) を返す。
• メイン処理では dfs(0, 0) の結果を返します。

ポイントは、dfs(i, j+1) で「j 番目の位置を使わずにスキップする」場合と、dfs(i+1, j+1) * d[j][target[i]] で「j 番目の位置にある target[i] と一致する文字のうち 1 つを使う」場合の合計を取っている点です。事前に位置ごとの文字の出現回数を Counter で集計しておくことで、一致する文字の選び方の数を即座に参照できます。

Python 実装例

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

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))

入力

words = ["pqqp", "qppq"], target = "qpq"

出力

4

補足:計算量の改善

上記の素朴な DFS は、入力サイズによっては指数時間かかる可能性があります。実践的には functools.lru_cache などでメモ化を追加するか、「dp[i][j] = target の i 文字目以降を、位置 j 以降の文字で作る方法の数」という二次元 DP に書き換えることで、計算量を O(n × m) まで抑えられます。位置ごとの文字数を前計算しておけば、状態遷移は定数時間で行えるためです。