Hints — p39 Word Search

Hint 1. Try every cell as the potential starting point of the word. For each start, DFS into 4 neighbors looking for word[1], then word[2], …

Hint 2. Recursion signature: dfs(r, c, i) — currently at (r, c), trying to match word[i]. Base cases:

  • i == len(word): SUCCESS, return True.
  • out of bounds OR board[r][c] != word[i]: FAIL, return False.

Hint 3. Same cell can’t be reused. Two options:

  • Separate visited: set of (r, c) tuples — add before recurse, remove after.
  • In-place sentinel: temporarily overwrite board[r][c] = '#', restore on return.

The in-place trick saves O(R·C) memory AND is the standard answer.

Hint 4. The 4-direction template:

DIRS = ((-1,0),(1,0),(0,-1),(0,1))
for dr, dc in DIRS:
    if dfs(r+dr, c+dc, i+1): return True

Hint 5. Tempting to memoize on (r, c, i) — DON’T. The valid-paths depend on which cells are already used (visited state), which is exponential. Memoization is unsound here.

If still stuck: see solution.py.