파이썬에서 단어 검색

2D 보드와 단어가 있다고 가정하면 해당 단어가 그리드에 있는지 여부를 찾아야 합니다. 단어는 순차적으로 인접한 셀의 문자로 만들 수 있으며 "인접" 셀은 가로 또는 세로로 인접한 셀입니다. 같은 문자 셀을 두 번 이상 사용해서는 안 됩니다. 따라서 행렬이 다음과 같은 경우 -

"ABCCED"라는 단어가 주어지면 대답은 true가 되고 "SEE"라는 단어는 true가 되지만 "ABCB"는 false가 됩니다.

단계를 살펴보겠습니다 -

• 재귀적 접근 방식을 사용하여 이 문제를 해결할 것입니다. 따라서 재귀 메서드 이름이 find()라고 하면 행렬 매트, 단어, 행, 열 및 인덱스 i를 사용합니다. 처음에 인덱스 i =0
• i =단어 길이인 경우 True 반환
• 행>=매트 또는 행의 행 개수 <0 또는 열>=매트 또는 열의 열 개수 <0 또는 단어[i]가 mat[row, col]과 같지 않으면 false를 반환합니다.
• 매트[행, 열] :=“*”
• 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) 또는 찾기(매트, 단어, 행, 열 - 1, i + 1)
• 매트[행, 열] :=단어[i]
• 반환 결과
• 주요 작업은 다음과 같이 수행됩니다. -
• n :=행 수 및 m :=열 수
• 0~n
  범위의 i에 대해
  • 0 ~ m
    범위의 j에 대해
    • 단어[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