Problem. Given a 2D grid of characters and a word, return True if the word can be formed by moving horizontally or vertically through adjacent cells without reusing a cell.
This is the classic grid DFS with backtracking pattern.
Examples:
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],word = "ABCCED"→Trueboard = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],word = "SEE"→Trueboard = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],word = "ABCB"→False
Solution. Launch a DFS from every cell that matches the first letter. Temporarily mark a cell as used during the current path, recurse into neighbors for the next letter, and restore the cell on the way back.
def exist(board, word):
rows = len(board)
cols = len(board[0])
def dfs(row, col, index):
if index == len(word):
return True
if row < 0 or row >= rows or col < 0 or col >= cols:
return False
if board[row][col] != word[index]:
return False
saved = board[row][col]
board[row][col] = '#'
found = (
dfs(row + 1, col, index + 1)
or dfs(row - 1, col, index + 1)
or dfs(row, col + 1, index + 1)
or dfs(row, col - 1, index + 1)
)
board[row][col] = saved
return found
for row in range(rows):
for col in range(cols):
if dfs(row, col, 0):
return True
return False
O(m * n * 4^L) worst-case time for word length L, O(L) recursion stack.
Gotchas.
- You must restore the cell after exploring a path, or later starts will see a corrupted board.
- The same cell cannot be reused within one word path.
- Early letter-frequency pruning can speed up large instances, but the core DFS is usually what interviewers want first.