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

4 x 4の文字ボードと単語のリストがあるとすると、単語ごとに最大1つのセルを使用して、隣接する文字のシーケンスによってボード内で生成できる単語の最大数を見つける必要があります（ただし、言い換えれば、セルを再利用できます）。上、下、左、右、または斜めの方向に移動できます。

したがって、入力が次のような場合

words =["bat"、 "far"、 "mat"]の場合、出力は3になります。これは、mat [0,1]→[1,1]→[2,0]、bat [0、 2]→[1,1]→[2,2]、および遠い[0,2]→[1,3]→[2,3]。

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

• N：=Aの行数、M：=Aのサイズの列数

• trie：=新しいマップ

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

  • 現在：=トライ

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

    • cが電流の場合、

      • current：=current [c]

    • それ以外の場合

      • current [c]：=新しいマップ

      • current：=current [c]

  • current ["*"]：=True

• ans：=0

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

• 「*」がdにある場合、

  • d ["*"]

    を削除します

  • ans：=ans + 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の範囲のiの場合、実行

  • 0からMの範囲のjについては、次のようにします

    • A [i] [j]がトライの場合、

      • 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