给定 word = "ABCCED", 返回 true. 给定 word = "SEE", 返回 true. 给定 word = "ABCB", 返回 false.
解答
感觉可以回溯，但不知道怎么找第一个字母。走过的路可以直接覆盖掉原来的board。
回溯
他的意思是，直接用递归，遇到错的就减枝。也不用管第一个字母在哪，就从左上角算到右下角😂
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if not word:
return False
row = len(board)
col = len(board[0])
direction = [(-1, 0), (1, 0), (0, 1), (0, -1)]
def backtrack(i, j, target, visited):
if target == len(word):
return True
for x, y in direction:
tmp_i, tmp_j = x+i, y+j
if 0 <= tmp_i and tmp_i < row and 0 <= tmp_j and tmp_j < col\
and (tmp_i, tmp_j) not in visited and board[tmp_i][tmp_j] == word[target]:
visited.add((tmp_i, tmp_j))
if backtrack(tmp_i, tmp_j, target+1, visited):
return True
visited.remove((tmp_i, tmp_j))
return False
for i in range(row):
for j in range(col):
if board[i][j] == word[0] and backtrack(i, j, 1, {(i, j)}):
return True
return False
Runtime: 296 ms, faster than 90.55% of Python3 online submissions for Word Search.
Memory Usage: 13.8 MB, less than 100.00% of Python3 online submissions for Word Search.
原地算法
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if not word:
return False
row = len(board)
col = len(board[0])
def backtrack(x, y, target, board):
if x < 0 or x == row or y < 0 or y == col:
return False
if board[x][y] == "#" or board[x][y] != word[target]:
return False
if target == len(word)-1:
return True
tmp = board[x][y]
board[x][y] = "#"
flag = backtrack(x-1, y, target+1, board)\
or backtrack(x+1, y, target+1, board)\
or backtrack(x, y-1, target+1, board)\
or backtrack(x, y+1, target+1, board)
board[x][y] = tmp
return flag
for i in range(row):
for j in range(col):
if backtrack(i, j, 0, board):
return True
return False
Runtime: 312 ms, faster than 86.85% of Python3 online submissions for Word Search.
Memory Usage: 14 MB, less than 95.74% of Python3 online submissions for Word Search.