Pythonで文字グリッドから生成できる単語の数を数えるプログラム

問題の概要

4×4の文字ボードと単語のリストが与えられたとします。このとき、隣接する文字を順にたどることで、ボード上から生成できる単語の最大数を求める必要があります。1つの単語を作る際には同じマスを最大1回しか使用できませんが、異なる単語同士であればマスを再利用しても構いません。移動は上下左右に加え、斜め方向も含めた8方向が可能です。

入力例

words = ["bat", "far", "mat"] の場合、出力は 3 となります。これは、それぞれの単語を次の経路で生成できるためです。

• mat: [0,1] → [1,1] → [2,0]
• bat: [0,2] → [1,1] → [2,2]
• far: [0,2] → [1,3] → [2,3]

解法の手順

この問題を解くためには、以下の手順に従います。

• N := 行列Aの行数、M := 列数とします。
• trie := 新しい辞書(トライ木)を作成します。
• words 内の各単語 word について、以下を実行します。
  • current := trie とします。
  • word 内の各文字 c について、c が current に存在すれば current := current[c] とし、存在しなければ current[c] := 新しい辞書 を設定したうえで current := current[c] とします。
  • current["*"] := True を設定し、単語の終端を記録します。
• ans := 0 とします。
• 関数 dfs(x, y, d) を定義します。処理内容は以下の通りです。
  • d に "*" が含まれている場合、d["*"] を削除して ans := ans + 1 とします(単語が1つ見つかったことを意味します)。
  • temp := A[x][y] を保存し、A[x][y] := "#" として訪問済みマークを付けます。
  • [x-1, x, x+1] の各 i と [y-1, y, y+1] の各 j について、i と j が行列の範囲内にあり、かつ A[i][j] が d に存在する場合は、dfs(i, j, d[A[i][j]]) を再帰的に呼び出します。
  • A[x][y] := temp として元の値を復元します(バックトラック)。
• メイン処理では、0 から N-1 の各 i、0 から M-1 の各 j について、A[i][j] が trie に存在すれば dfs(i, j, trie[A[i][j]]) を呼び出します。
• 最後に ans を返します。

Pythonでの実装例

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

class Solution:
    def solve(self, A, words):
        N = len(A)
        M = len(A[0])
        trie = dict()
        for word in words:
            current = trie
            for c in word:
                if c in current:
                    current = current[c]
                else:
                    current[c] = dict()
                    current = current[c]
            current["*"] = True
        ans = 0
        def dfs(x, y, d):
            nonlocal ans
            if "*" in d:
                del d["*"]
                ans += 1
            temp = A[x][y]
            A[x][y] = "#"
            for i in [x - 1, x, x + 1]:
                for j in [y - 1, y, y + 1]:
                    if 0 <= i < N and 0 <= j < M and A[i][j] in d: dfs(i, j, d[A[i][j]])
            A[x][y] = temp
        for i in range(N):
            for j in range(M):
                if A[i][j] in trie:
                    dfs(i, j, trie[A[i][j]])
        return ans

ob = Solution()
matrix = [
    ["m", "b", "f", "d"],
    ["x", "a", "y", "a"],
    ["t", "z", "t", "r"],
    ["s", "q", "q", "q"]
]
words = ["bat", "far", "mat"]
print(ob.solve(matrix, words))

入力

[
["m", "b", "f", "d"],
["x", "a", "y", "a"],
["t", "z", "t", "r"],
["s", "q", "q", "q"] ],
["bat", "far", "mat"]

出力

3

まとめ

このアルゴリズムは、トライ木による単語の事前構築とDFS(深さ優先探索)によるバックトラックを組み合わせることで、ボード上のすべての開始位置から効率よく単語を探索できます。また、見つかった単語をトライ木から削除することで、同一単語の重複カウントも自動的に防いでいます。計算量を抑えつつ正確に結果を得られる、実用的なアプローチです。