The problem
Given a grid of letters and a word, decide whether the word can be traced through the grid by moving up, down, left or right, without using a cell twice.
Input: board = ABCE / SFCS / ADEE, word = "ABCCED" Output: true
Picture it
Picture tracing the word with your finger on a letter grid. Start on any cell matching the first letter. From there try each neighbour that matches the next letter. Cells you’re standing on are marked so you don’t reuse them. If you get stuck, lift your finger back one step (unmark the cell) and try another direction.
How to recognise it
- The input is a grid and you must find a path of neighbouring cells (up, down, left, right) that spells something.
- A cell may be used only once in a path, so the search needs memory of "cells on the current path".
- You do not know where the path starts, and many paths may begin the same way, so you must be able to retreat and try another direction.
- Small limits: a board of at most 6 × 6 cells and a word of at most 15 letters. The number of paths is exponential in the word length.
- Exploring one path to the end, then undoing it, is depth-first search with backtracking: mark the cell, explore, unmark.
Start with brute force
Generate every non-repeating walk of the right length from every cell, build the string each spells, and compare it with the word.
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def exist_brute(board, word):
R, C = len(board), len(board[0])
def walks(r, c, seen, s):
s += board[r][c]
if len(s) == len(word):
yield s
return
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in seen:
yield from walks(nr, nc, seen | {(nr, nc)}, s)
return any(w == word
for r in range(R) for c in range(C)
for w in walks(r, c, {(r, c)}, ""))
From each cell there are up to 4 × 3^(L − 1) walks of length L (4 first moves, then at most 3 because you cannot step back). For L = 15 that is about 1.9 × 10^7 per starting cell, and a 6 × 6 board has 36 start cells, around 7 × 10^8 walks, each building a string. Space is O(L) per walk plus the copies of seen.
From brute force to the idea
- Find the waste. The brute force keeps walking even after the letters stopped matching. If the word starts with
Aand the cell holdsB, nothing that follows can work. - Check as you go.
dfs(r, c, i)asks whetherword[i:]can be traced starting at cell(r, c). ReturnFalseat once if the cell is off the board or holds the wrong letter. - Succeed when the word is used up. If
i == len(word), every letter has been matched, so returnTrue. - Mark the cell as in use. Overwrite it with
"#"while exploring, so the same cell is not used twice. This saves a separateseenset. - Try the four neighbours and unmark.
any(...)stops at the first success. After the search, restoreboard[r][c] = word[i]so other paths can use it. - Try every cell as a start. The outer
anyrunsdfs(r, c, 0)for each cell.
This is the key idea: prune the moment a letter fails to match, and mark and unmark cells as you go.
The key idea
Depth-first search with backtracking: mark, explore 4 neighbours, unmark. Stop as soon as the whole word is matched.
Python solution
def exist(board, word):
R, C = len(board), len(board[0])
def dfs(r, c, i):
if i == len(word):
return True
if not (0 <= r < R and 0 <= c < C):
return False
if board[r][c] != word[i]:
return False
board[r][c] = "#" # mark: in use
found = any(dfs(r+dr, c+dc, i+1)
for dr, dc in DIRS)
board[r][c] = word[i] # unmark
return found
return any(dfs(r, c, 0)
for r in range(R)
for c in range(C))
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (all walks) | O(R · C · 3^L) walks, each also costs O(L) to build | O(L) per walk, plus the seen copies |
| Pruned DFS (shown code) | O(R · C · 3^L) in the worst case, but a mismatch ends a branch at once | O(L): recursion depth is at most L + 1 |
The worst case is a board where nearly every cell holds the same letter as the word. A 6 × 6 board of a with the word aaaaaaaaab (10 letters) took roughly a tenth of a second here, and each extra letter can multiply the work by up to 3. Ordinary boards finish almost instantly.
Edge cases
- Example (
ABCE / SFCS / ADEE):"ABCCED"and"SEE"are found, and"ABCB"is not, because it would reuse the sameB. - One cell (
[["a"]]):"a"is found;"aa"is not. - Word longer than the board has cells: the search simply fails, with no special check.
- Board is restored: after every call the board holds its original letters.
- Letters only: the marker
"#"assumes the board never contains#. The problem uses letters. - Constant
DIRS: the snippet definesDIRSafter the function. That works because it is read only whenexistruns. - Depth: recursion is at most 16 calls deep, so the recursion limit is never a concern.
Common mistakes
- Forgetting to unmark the cell. A failed attempt leaves
#behind, and a later path through that cell fails. On a 3 × 1 columna, b, band the wordbba, the answer comes backFalseinstead ofTrue. - Checking
i == len(word)after the board and letter tests, so a full match reads past the end of the word. - Starting the search only from one cell.
Return how many different paths spell the word, instead of a yes or no. Two paths are different if they visit different cells. Describe your approach, then write it if you like.
Compare with our answer
Keep the same mark, explore and unmark pattern. But instead of stopping at the first success, add up what each neighbour returns. Count a path when you match the last letter, then return without exploring further.
def count_paths(board, word):
R, C = len(board), len(board[0])
def dfs(r, c, i):
if not (0 <= r < R and 0 <= c < C) or board[r][c] != word[i]:
return 0
if i == len(word) - 1:
return 1
board[r][c] = "#"
total = sum(dfs(r + dr, c + dc, i + 1) for dr, dc in DIRS)
board[r][c] = word[i]
return total
return sum(dfs(r, c, 0) for r in range(R) for c in range(C))
On a 2 × 2 board of a with the word aaa the answer is 8. Worst-case time is still O(R · C · 3^L), and space O(L).
A strong answer mentions: summing instead of any, counting at the last letter, and why every explored branch must be unmarked.
1. A game board is a 5 × 5 grid of tiles, and a player drags a finger between touching tiles (not diagonally) to spell a word, never reusing a tile. How should the game check a word?
The path can turn, so you must explore neighbours and retreat when a branch fails. Rows and columns catch only straight words, sorting loses the positions, and a set of touching pairs does not stop a tile from being reused.
2. Why does the shown code stop exploring a branch the moment board[r][c] != word[i]?
Every walk through a mismatching cell is invalid, so thousands of continuations are never generated. That check is the whole saving over the brute force. The board is not sorted, a marked cell shows #, not a letter, and any stops only after a success.
3. A learner deletes the line board[r][c] = word[i] that unmarks the cell. Which test is now answered wrongly?
In the column, the search starts at the first b, goes down to the second b, finds no a, and returns with both cells still marked #. The correct path starts at the lower b, which is now blocked, so the answer comes back False. The other tests succeed on their first attempt.
Score 60% or more and the lesson is marked complete.