Description
Find whether a nonempty word can be traced through orthogonally adjacent board cells without reusing a cell.
Solution
def exist(board, word):
rows, cols = len(board), len(board[0])
def walk(r, c, i):
if i == len(word):
return True
if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[i]:
return False
saved, board[r][c] = board[r][c], '#'
found = any(walk(r+dr, c+dc, i+1) for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)))
board[r][c] = saved
return found
return any(walk(r,c,0) for r in range(rows) for c in range(cols))Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[["A","B"],["C","D"]],"ABD"]- Output
true
A to B to D follows adjacent cells.
Example 2
- Input
[[["A"]],"AA"]- Output
false
The sole cell cannot be used twice.
Example 3
- Input
[[["Z"]],"Z"]- Output
true
The starting cell already matches the entire word.
Approach
Start DFS at every cell, temporarily marking visited cells and restoring them afterward.
Time & space
O(R C 4^L) upper-bound time; O(L) recursion space, for word length L.