Word Search
Find whether a word can be traced through adjacent cells of a letter grid, marking each cell on the way down and restoring it on the way back.
Examples
A → B → C → C → E → D, starting from the top-left cell.
From the S on the right edge: down to E, then left to E.
The second B would have to be the same cell as the first.
Problem Understanding
Return true if word can be spelled out on the m x n letter grid board by stepping from each letter to the next through cells that touch up, down, left or right.
Diagonal steps are not allowed, and no cell may be used twice in the same word.
Algorithm Strategy
Grid DFS with an undo — backtracking on a board.
- Try every start. Call
backtrack(r, c, 0)from each cell in row order, and stop at the first that returns true. - Finished? If
ihas run past the last letter, every letter is on the path: return true. - Reject. Return false for a position off the board, or a cell whose letter is not
word[i]— which includes a cell marked#, because#is never a letter of the word. - Mark. Write
#into the cell, so no deeper call on this path can use it again. - Explore. Try the four neighbours — down, up, right, left — with
i + 1. The first one that returns true setsfoundand breaks. - Unmark. Write the letter back before returning
found.
Marking the board in place is what saves a separate visited set; writing the letter back is what makes that safe.
Interactive Visualization
The board is drawn exactly as the code holds it. A cell on the current path shows #, because that is what the code has written into it; the letter comes back, in amber, on the step that writes it back. The arrow is the call about to be made, a rejected cell flashes red with the reason, and a call that steps off the board lands on an empty cell outside it before returning.
Try Undo matters: the first path from the top-left A fails, and the second start only succeeds because the first one wrote its letters back.
Dry Run
Tracing board = [["A","B"],["C","D"]], word = "ABD". Directions are tried down, up, right, left.
| # | Call | Board after | What happens |
|---|---|---|---|
| 1 | backtrack(0,0,0) |
#B / CD |
A = word[0]: mark it |
| 2 | backtrack(1,0,1) |
#B / CD |
Down: C is not B — false |
| 3 | backtrack(-1,0,1) |
#B / CD |
Up: off the board — false |
| 4 | backtrack(0,1,1) |
## / CD |
Right: B = word[1]: mark it |
| 5 | backtrack(1,1,2) |
## / C# |
Down: D = word[2]: mark it |
| 6 | backtrack(2,1,3) |
## / C# |
Down: i = 3 = length — true |
| 7 | backtrack(1,1,2) |
## / CD |
Found: break, write D back, return true |
| 8 | backtrack(0,1,1) |
#B / CD |
Found: break, write B back, return true |
| 9 | backtrack(0,0,0) |
AB / CD |
Found: break, write A back, return true |
The outer loop returns true, and the board is exactly as it was given.
For word = "ABA" the path reaches B and then tries left, back into (0,0) — which reads #, not A, so that call returns false. That is the mark doing its job: the same A cannot be used twice.
Edge Cases & Common Mistakes
Watch out for these pitfalls:
Forgetting to write the letter back: a failed branch then leaves
#s on the board, and a later path that needs those cells can never be found. The Undo matters preset in the figure fails without it.Slicing the word: passing
word[1:]down copies the rest of the word on every call. Pass the indexiinstead.Checking the end too late: test
i == len(word)before the bounds check. The last letter is matched one call earlier, and the call after it may be off the board.Cheap pruning: before searching, count each letter in the board; if the word needs more of any letter than the board has, return false at once.
Solution
One algorithm in all six languages — the lines light up as the figure above steps.
Word Search Code
1var exist = function(board, word) {2 const rows = board.length, cols = board[0].length;3 const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];45 const backtrack = (r, c, i) => {6 if (i === word.length) {7 return true;8 }9 if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[i]) {10 return false;11 }12 board[r][c] = '#';13 let found = false;14 for (const [dr, dc] of dirs) {15 if (backtrack(r + dr, c + dc, i + 1)) {16 found = true;17 break;18 }19 }20 board[r][c] = word[i];21 return found;22 };2324 for (let r = 0; r < rows; r++) {25 for (let c = 0; c < cols; c++) {26 if (backtrack(r, c, 0)) {27 return true;28 }29 }30 }31 return false;32};