2D 보드와 단어 목록이 있다고 가정합니다. 그래서 사전에서 칠판에 있는 모든 단어를 찾아야 합니다. 여기서 각 단어는 순차적으로 인접한 셀의 문자로 구성되어야 하며, 여기서 인접한 셀은 수평 또는 수직으로 인접한 셀입니다. 동일한 문자 셀이 한 단어에서 두 번 이상 사용될 수 없음을 명심해야 합니다.
따라서 입력이 다음과 같은 경우 -
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
배열 결과 만들기
-
solve()라는 메서드를 정의합니다. 이것은 board, d, i, j s를 사용합니다.
-
i 또는 j가 각각 보드 행 및 열 범위에 없으면 false를 반환합니다.
-
l :=보드[i, j]
-
l이 d에 있으면
-
d :=d[l], l을 s와 연결
-
#이 d에 있고 d[#]가 null이 아니면
-
결과에 s 삽입
-
세트 d[#] :=0
-
-
보드[i, j] :=*
-
i+1 <보드의 행 수 및 d의 보드[i + 1, j]이면
-
해결 호출(보드, d, i + 1, j, s)
-
-
j+1 <보드의 열 수 및 d의 보드[i, j+1]이면
-
해결 호출(보드, d, i, j+1, s)
-
-
i-1> 0이고 d에서 board[i - 1, j]이면
-
해결 호출(보드, d, i - 1, j, s)
-
-
j-1> 0이고 d에서 board[i, j-1]이면
-
해결(board, d, i, j-1, s) 호출
-
-
보드[i, j] :=l
-
-
insert()라는 하나의 메서드를 정의하면 단어와 사전이 필요합니다. t
-
현재 :=t
-
나는 단어로
-
i가 현재 상태가 아니면 current[i] :=new map
-
현재 :=현재[i]
-
-
현재[#] :=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']