Word Search in a Grid: Backtracking Done Right in a Coding Interview
3 views
"Given an m x n grid of letters and a word, return true if the word can be formed by sequentially adjacent cells" is a classic coding interview problem. Adjacent means up, down, left or right, and a cell may be used only once per word. It is the cleanest way for an interviewer to see whether you can write correct backtracking on a grid without bugs.
The approach
Try every cell as a starting point. From a cell that matches word[i], recursively look for word[i + 1] in the four neighbors. Mark the current cell as visited before recursing and unmark it afterward, which is the "backtrack" step.
def exist(board, word):
rows, cols = len(board), len(board[0])
def dfs(r, c, i):
if i == len(word):
return True
if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != word[i]:
return False
tmp, board[r][c] = board[r][c], '#' # mark visited
found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1) or
dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
board[r][c] = tmp # backtrack
return found
return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))
Key details interviewers check
- Restore the cell in every path, including when found is True; otherwise the board is corrupted for the caller.
- Check bounds before reading the cell.
- Marking in place with a sentinel avoids an extra visited set; mention you can use a set if modifying input is not allowed.
- The base case i == len(word) comes before the bounds check so a word that ends on the edge still succeeds.
Complexity
Time is O(m * n * 3^L), where L is the word length: from each cell you explore at most three new directions after the first step, because you never go back to where you came from. Space is O(L) for the recursion stack.
Pruning tricks worth mentioning
1. If the word is longer than m * n, return False immediately.
2. Count letters: if the board does not contain enough of some character, return False.
3. Reverse the word if its last character is rarer on the board than its first, so the search fails faster.
These do not change worst-case complexity but make real inputs much faster, and interviewers like hearing them.
The big follow-up: Word Search II
"Given a list of words, return all that appear on the board." Running the single-word search for each word is too slow. Build a trie of all words, then run one DFS per cell that walks the trie alongside the grid. Store the complete word at trie end nodes, add it to the result when reached, and remove it (or prune empty trie branches) to avoid duplicates and wasted work.
How to present it
Explain the brute-force start-from-every-cell idea, write the DFS with explicit mark and restore steps, give the complexity, then mention pruning and the trie extension. Talking through one small example, such as finding "SEE" in a 3 x 4 board, shows the interviewer you understand the visited logic.
If recursion questions make you lose your thread under pressure, Linkjob AI (https://linkjob.ai) gives real-time help during job interviews and technical interviews, so you can keep your reasoning clear as the interviewer asks follow-ups.