?解法:
? ? ? ? 和机器人活动范围思想类似。
class Solution:
def Core(self, board, m,n,i,j,word,path,visited):
if path == len(word):
return True
hasPath = False
if i>=0 and i<m and j>=0 and j<n and board[i][j] == word[path] and visited[i][j] == 0:
path = path + 1
visited[i][j] = 1
hasPath = self.Core(board, m,n,i-1,j,word,path,visited) or self.Core(board, m,n,i+1,j,word,path,visited) or self.Core(board, m,n,i,j-1,word,path,visited) or self.Core(board, m,n,i,j+1,word,path,visited)
if hasPath == False:
path = path - 1
visited[i][j] = 0
return hasPath
def exist(self, board: List[List[str]], word: str) -> bool:
import numpy as np
if board==[] or word=='':
return False
board = np.array(board)
m,n = board.shape
if m<1 or n<1:
return False
visited = np.array([[0]*n for _ in range(m)])
path = 0
for i in range(m):
for j in range(n):
if self.Core(board, m,n,i,j,word,path,visited):
return True
return False
?
|