LC 0079 [M] Word Search - ALawliet/algorithms GitHub Wiki
DFS from each point
we mutate the original board to track visited so we need to pass it in as state
we pass in the word as state and check the first char, then recurse on the rest of the word suffix
class Solution:
def exist(self, board, word):
if not board:
return False
n_rows = len(board)
n_cols = len(board[0])
def dfs(board, r, c, word):
if len(word) == 0: # all the characters are checked so found the word
return True
# out of bounds or no match, stop exploring this path
if r < 0 or r >= n_rows or c < 0 or c >= n_cols or word[0] != board[r][c]:
return False
tmp = board[r][c] # first character is found, check the remaining part
board[r][c] = '!' # avoid visit agian
# check whether can find "word" along one direction
res = any([ # 'or each dir
dfs(board, r+1, c, word[1:]),
dfs(board, r-1, c, word[1:]),
dfs(board, r, c+1, word[1:]),
dfs(board, r, c-1, word[1:])
])
board[r][c] = tmp
return res
for r in range(n_rows):
for c in range(n_cols):
if dfs(board, r, c, word):
return True
return False