Can you spell a word through neighbouring letters in a grid? Try each path, mark the cells you use, and unmark them when you back out.
▼The problem
LeetCode 79 (Medium). Given an m × n grid of letters and a word, return whether the word can be spelled by a path of horizontally or vertically adjacent cells, using each cell at most once.
Example (from the problem statement): the board [[A,B,C,E],[S,F,C,S],[A,D,E,E]]. "ABCCED" → true (across the top, down, then back along the bottom); "ABCB" → false (the only B next to that C is the B already on the path); "SEE" → true (the walkthrough: the first S at (1,0) has no E beside it; the S at (1,3) goes up to the E at (0,3), a dead end, then down to (2,3) and left to (2,2)).
The solution
def exist(board, word):
R, C = len(board), len(board[0])
lit = set()
def dfs(r, c, k):
if k == len(word): return True
if not (0 <= r < R and 0 <= c < C): return False
if (r, c) in lit or board[r][c] != word[k]: return False
lit.add((r, c)) # light it
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
if dfs(r + dr, c + dc, k + 1): return True
lit.remove((r, c)) # dead end: put it out
return False
return any(dfs(r, c, 0) for r in range(R) for c in range(C))Transcript
Word Search. Given a grid of letters and a word, can you spell the word by stepping between neighboring cells, using each cell at most once?
Here, A, B, C, C, E, D is there: across, down, then back along the bottom. But A, B, C, B is not: the only B next to that C is already used.
Checking every path is hopeless: four directions at every step. Most paths go wrong by the second letter, so stop them early.
Think of a dark dungeon. Stand on a tile with the first letter and light it. Step to a neighbor only if it holds the next letter, and light that too. Lit tiles are your path, so none is reused. At a dead end, put the light out and step back. That's backtracking.
In code, a helper takes a cell and how many letters match so far. If that's all of them, return true. If the cell is off the grid, lit, or the wrong letter, return false. Otherwise light it, try the four neighbors, and unlight it if none works. Start from every cell.
Let's search for S, E, E. The first S has no E beside it, so it goes dark. The second S has an E above. But that E has no fresh E around it: dead end, so it goes dark. Back at S, try below: E, then E to the left. Found it.
For an m by n grid and a word of L letters, every cell can start, and each step has at most three new ways to go. So the time is m times n times three to the L. The recursion is only L deep.
Light a tile, try its neighbors, step back. That's Word Search.