Word Search

Word Search moves backtracking onto a grid. The choices at each step are the four neighbours of the current cell, the state is "which cells are on the current path", and the finish rule is "the path spells the whole word".

It is also the clearest case of pruning by the data itself: a wrong letter ends the branch after a single comparison.

The problem

You are given a grid of letters and a word. Return True if the word can be spelled by a path of cells, where each step moves up, down, left or right, and no cell is used twice in the same path.

Using this board:

C A T SO R E AD O G S

• "CORE" → True. C (0,0) → O (1,0) → R (1,1) → E (1,2).
• "TEAR" → False. T (0,2) → E (1,2) → A (1,3), and A's neighbours are S, S and the E already used. No R.

Constraints: 1 ≤ rows, cols ≤ 6, 1 ≤ word length ≤ 15, upper- and lower-case English letters.

Clarifying questions

• Diagonal moves? No, only the four directions.
• Can a cell be reused? Not within one path. It can be reused by a different path.
• Case-sensitive? Yes: a and A differ.
• May I change the board? Assume yes, as long as it is restored before returning. If not, use a separate visited set.

Approach 1: the simple way — walk every path, compare at the end

From every cell, walk every path of len(word) cells that does not revisit a cell. When a path is full length, compare its letters with the word.

1def exist_brute(board: list[list[str]], word: str) -> bool:2    """Walk every simple path of len(word) cells; compare at the end."""3    rows, cols, length = len(board), len(board[0]), len(word)45    def walk(r: int, c: int, path: list[str], seen: set) -> bool:6        path.append(board[r][c]); seen.add((r, c))7        found = len(path) == length and "".join(path) == word8        if len(path) < length:9            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):10                if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen:11                    if walk(nr, nc, path, seen):12                        found = True13                        break14        path.pop(); seen.discard((r, c))15        return found1617    return any(walk(r, c, [], set()) for r in range(rows) for c in range(cols))

Why it is too slow. Every cell starts up to 4 × 3^(L−1) paths of length L. On a 6 × 6 board with a 7-letter word that is about 36 × 4 × 3⁶ ≈ 105,000 full paths — and with L = 15 it is over 600 million. Almost all of them are dead after one letter: if the board is mostly A and the word starts with Z, the code still walks every path before comparing.

The key insight

Compare letter by letter as you go. A path is only worth extending while its letters match the start of the word. The first mismatch kills the branch, together with everything below it.

That turns the check into a prune at the top of each call: if the current cell is off the board, already used, or holds the wrong letter, return False at once. On a real board most starting cells fail on the very first comparison, and most of the rest fail within two or three letters.

To mark "already on this path" without a separate set, overwrite the cell with a character that can never match, such as #, and write the letter back after exploring. That write-back is the undo step.

Approach 2: backtracking with in-place marking

1def exist(board: list[list[str]], word: str) -> bool:2    """True if word can be traced through adjacent cells, each used once."""3    rows, cols = len(board), len(board[0])45    def dfs(r: int, c: int, k: int) -> bool:6        if k == len(word):7            return True                          # matched every letter8        if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[k]:9            return False                         # off the board or wrong letter: prune10        saved, board[r][c] = board[r][c], "#"    # choose: mark as used11        found = (dfs(r + 1, c, k + 1) or dfs(r - 1, c, k + 1) or12                 dfs(r, c + 1, k + 1) or dfs(r, c - 1, k + 1))13        board[r][c] = saved                      # undo: restore the letter14        return found1516    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

The state is (r, c, k): the cell we stand on and which letter of the word it must match. A used cell holds #, which never equals a letter, so the "wrong letter" test also catches "already used". The or chain stops at the first direction that succeeds, and any stops at the first starting cell that succeeds.

Dry run for "CORE". Neighbours are tried in the order down, up, right, left:

Every marked cell is restored as the calls return, so the board ends exactly as it started.

Complexity. From each of the R × C starting cells the search goes at most L deep. The first step has 4 directions; every later step has at most 3, since the cell we came from is marked. So the time is O(R × C × 3^L) in the worst case — for example a board of all A and a word AAAA…AB. In practice the letter prune makes it far smaller. Working space is O(L) for the recursion; the marking is done in the board itself.

Approach 3: reject before you search

Two cheap checks, run once before the search, remove the worst cases:

1from collections import Counter23def exist_fast(board: list[list[str]], word: str) -> bool:4    """Word Search with two checks before the search starts."""5    have = Counter(ch for row in board for ch in row)6    need = Counter(word)7    if any(have[ch] < k for ch, k in need.items()):8        return False                         # the board lacks a letter: no search9    if have[word[0]] > have[word[-1]]:10        word = word[::-1]                    # start from the rarer end11    return exist(board, word)

The letter count check answers "TEAR"-style questions with no search at all when a letter is missing or too rare. Reversing the word when its first letter is common and its last letter is rare means fewer starting cells survive the first comparison. Both leave the worst-case bound unchanged, but they defeat the inputs interviewers use to test for it, such as a board full of A and a word ending in a letter that is not there.

Edge cases

• Word longer than rows × cols — can never fit; the count check rejects it, since some letter is needed more times than the board holds.
• One-cell board — works: the call at (0,0) matches or not, and all four neighbours are off the board.
• A word that would need one cell twice — on the one-row board A B, the word "ABA" must be False. The # mark on the A makes the return step fail, which is correct.
• Forgetting to restore — the next starting cell would see # where letters should be, and valid words would be missed.

Follow-ups

• Many words at once (Word Search II) — do not run this once per word. Put all words in a trie and walk the board once, following trie children; see the Tries section.
• Diagonal moves allowed — eight directions instead of four; the bound becomes O(R × C × 7^L).
• Return the path, not just True — keep a list of cells alongside the marks and copy it when k == len(word).