Pythonでの単語検索

2Dボードと単語があるとすると、その単語がグリッドに存在するかどうかを確認する必要があります。単語は、連続して隣接するセルの文字から作成できます。「隣接する」セルは、水平方向または垂直方向に隣接するセルです。同じ文字セルを複数回使用しないでください。したがって、行列が-

「ABCCED」という単語が与えられた場合、答えは真になります。「SEE」という単語の場合は真になりますが、「ABCB」の場合は偽になります。

手順を見てみましょう-

• 再帰的アプローチを使用してこれを解決します。したがって、再帰的なメソッド名がfind（）と呼ばれる場合、これは行列mat、word、row、col、およびindexiを取ります。最初はインデックスi=0
• i =単語の長さの場合、Trueを返します
• 行>=マットの行数または行<0または列>=マットの列数または列<0またはword[i]がmat[行、列]と同じでない場合、falseを返します
• mat [row、col]：=“ *”
• res：=find（mat、word、row + 1、col、i + 1）またはfind（mat、word、row-1、col、i + 1）またはfind（mat、word、row、col + 1、i + 1）またはfind（mat、word、row、col -1、i + 1）
• mat [row、col]：=word [i]
• return res
• メインタスクは次のように実行されます-
• n：=行数およびm：=列数
• 0からnの範囲のiの場合
  • 0からmの範囲のjの場合
    • if word [0] =mat [i、j]
      • find（mat、word、i、j）がfalseでない場合は、trueを返します

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

例

class Solution(object):
   def exist(self, board, word):
      n =len(board)
      m = len(board[0])
      for i in range(n):
         for j in range(m):
            if word[0] == board[i][j]:
               if self.find(board,word,i,j):
                  return True
      return False
   def find(self, board,word,row,col,i=0):
      if i== len(word):
         return True
      if row>= len(board) or row <0 or col >=len(board[0]) or col<0 or word[i]!=board[row][col]:
         return False
      board[row][col] = '*'
      res = self.find(board,word,row+1,col,i+1) or self.find(board,word,row-1,col,i+1) or self.find(board,word,row,col+1,i+1) or self.find(board,word,row,col-1,i+1)
      board[row][col] = word[i]
      return res
ob1 = Solution()
print(ob1.exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],"SEE"))

入力

[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
"SEE"

出力

True