Pythonでの単語検索II

2Dボードと単語のリストがあるとします。したがって、辞書から、ボード内のすべての単語を見つける必要があります。ここで、各単語は、連続して隣接するセルの文字から構成する必要があります。隣接するセルは、水平方向または垂直方向に隣接するセルです。同じ文字セルを1つの単語で複数回使用することはできないことに注意する必要があります。

したがって、入力が-

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

• 配列の結果を作成する

• Solve（）というメソッドを定義します。これには、board、d、i、j s

  が必要です。

• iまたはjのいずれかがそれぞれボードの行と列の範囲にない場合、falseを返します

• l：=ボード[i、j]

• lがdに存在する場合、

  • d：=d [l]、lをsと連結

  • ＃がdにあり、d [＃]がnullでない場合、

    • 結果にsを挿入

    • set d [＃]：=0

  • board [i、j]：=*

  • i + 1<ボード内の行数およびd内のボード[i+1、j]の場合、

    • 呼び出しsolve（board、d、i + 1、j、s）

  • j + 1 <ボード内の列数およびd内のボード[i、j + 1]の場合、

    • 呼び出しsolve（board、d、i、j + 1、s）

  • i-1> 0で、dにboard [i-1、j]がある場合、

    • 呼び出しsolve（board、d、i --1、j、s）

  • j-1> 0で、dにboard [i、j-1]がある場合、

    • 呼び出しsolve（board、d、i、j-1、s）

  • board [i、j]：=l

• insert（）と呼ばれる1つのメソッドを定義します。これには、単語と辞書が必要です。

• 現在：=t

• for i in word

  • iが現在ではない場合、current [i]：=new map

  • current：=current [i]

• current [＃]：=1

• メインの方法から、次のようにします-

• マップを作成するt

• 単語内の単語の場合：insert（word、t）

  を呼び出します

• ボード内のセルi、jごとに-solve（board、t、i、j）を呼び出します

• 結果を返す

例

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

class Solution(object):
   def findWords(self, board, words):
      self.result = []
      t = {}
      for word in words:
         self.insert(word,t)
      for i in range(len(board)):
         for j in range(len(board[0])):
            self.solve(board,t,i,j)
      return self.result
   def solve(self,board,d,i,j,s=""):
      if i<0 or j<0 or i>=len(board) or j>=(len(board[0])):
         return
      l = board[i][j]
      if l in d:
         d = d[l]
         s+=l
         if "#" in d and d['#']:
            self.result.append(s)
            d['#'] = 0
         board[i][j] = '*'
         if i+1<len(board) and board[i+1][j] in d :
            self.solve(board,d,i+1,j,s)
         if j+1 < len(board[0]) and board[i][j+1] in d:
            self.solve(board,d,i,j+1,s)
         if i-1>=0 and board[i-1][j] in d :
            self.solve(board,d,i-1,j,s)
         if j-1>=0 and board[i][j-1] in d :
            self.solve(board,d,i,j-1,s)
         board[i][j] = l
   def insert(self, word,t):
      current = t
      for i in word:
         if i not in current:
            current[i] = {}
         current =current[i]
      current['#']=1

ob = Solution()
print(ob.findWords([["o","a","a","n"],["e","t","e","a"],["i","h","k", "r"],["i","f","l","v"]],["oath","pea","tea","rain"]))

入力

[["o","a","a","n"],
["e","t","e","a"],
["i","h","k","r"],
["i","f","l","v"]],
["oath","pea","tea","rain"]

出力

['oath', 'tea']