{% tabs %} {% tab title="py again" %}
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if not word :
return True
visited = [[False] * len(board[0]) for _ in range(len(board))]
for i in range(len(board)):
for j in range(len(board[0])):
if self.dfs(0, board, word, i, j , visited):
return True
return False
def dfs(self, idx, board, word , x, y ,visited):
if idx == len(word):
return True
if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]) or visited[x][y] or board[x][y] != word[idx]:
return False
visited[x][y] = True
res = []
for dx, dy in [(0,1) , (0,-1), (1 , 0), (-1 , 0)]:
newx = dx + x
newy = dy + y
res.append(self.dfs(idx + 1, board, word, newx, newy, visited))
visited[x][y] = False
return sum(res)>0
{% endtab %}
{% tab title="Python" %}
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
N, M = len(board),len(board[0])
visited = [[0] * M for _ in range(N)]
print(visited)
for i in range(N):
for j in range(M):
if self.dfs(board,word,0,i,j,visited):
return True
return False
def dfs(self,board, word,idx, i, j,visited):
N, M = len(board),len(board[0])
# 终止条件
if idx == len(word):
return True
if i < 0 or i >= N or j < 0 or j >= M or visited[i][j] or board[i][j] != word[idx]:
return False
## 来过, 下一层, 取消
visited[i][j] = True
res = self.dfs(board, word ,idx +1, i+1, j,visited) or self.dfs(board, word ,idx +1, i-1, j,visited) or self.dfs(board, word ,idx +1, i, j+1,visited) or self.dfs(board, word ,idx +1, i, j -1,visited)
visited[i][j] = False
return res
{% endtab %} {% endtabs %}