Medium Backtrack+Prune Backtracking
In plain English: Check if you can spell a word by tracing a path through adjacent cells in a grid (each cell used once).
DFS from each cell matching the first letter. Mark cells as visited during the search and unmark on backtrack — prune when characters do not match.
Prompt
Given a 2D board of characters and a word, determine if the word exists in the grid. You can move up, down, left, right and cannot reuse a cell.
Try to write it from scratch before scrolling down.
Solution
def exist(board, word):
m, n = len(board), len(board[0])
def dfs(i, j, k):
if k == len(word):
return True
if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]:
return False
tmp, board[i][j] = board[i][j], '#' # mark visited
found = any(dfs(i+di, j+dj, k+1) for di, dj in [(-1,0),(1,0),(0,-1),(0,1)])
board[i][j] = tmp # backtrack
return found
return any(dfs(i, j, 0) for i in range(m) for j in range(n))
# Test: exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED") == True