LeetCode 212 · Tries

Word Search II, explained with a picture

A word-search puzzle guided by a trie.

HardTries
▶ Watch it step by step

The problem

Given a grid of letters and a list of words, return every word that can be traced in the grid by moving up, down, left or right, without using the same cell twice in a word.

Input:  board = oaan / etae / ihkr / iflv, words = [oath, pea, eat, rain]
Output: ["oath", "eat"]

Picture it

Picture a word-search puzzle. Searching for each word separately repeats a lot of work. Instead we put all the words in a letter tree (trie). Then from each cell we walk the grid and the trie together: we only keep walking while the letters so far are the start of some word. The moment no word continues, we turn back.

How to recognise it

  • You trace paths through a grid (up, down, left, right, no cell twice), which is backtracking: step into a cell, explore, then undo the step.
  • There are many words to look for at once, and they share prefixes. Searching for each word separately repeats the same walks.
  • A trie lets one walk check all words at the same time: the path so far must be a prefix of some word, or the walk can stop.
  • The board is at most 12 × 12, but there can be 3 × 10^4 words of up to 10 letters.

Start with brute force

Run the single-word search (LeetCode 79) once for every word.

def exist(board, word):
    R, C = len(board), len(board[0])
    def dfs(r, c, k):
        if k == len(word):
            return True
        if not (0 <= r < R and 0 <= c < C) or board[r][c] != word[k]:
            return False
        board[r][c] = "#"
        ok = any(dfs(r + dr, c + dc, k + 1)
                 for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
        board[r][c] = word[k]
        return ok
    return any(dfs(r, c, 0) for r in range(R) for c in range(C))

def find_words_brute(board, words):
    return [w for w in words if exist(board, w)]

One word costs up to O(R · C · 4 · 3^(L − 1)): every start cell, then at most three new directions per step. With 3 × 10^4 words that is already 3 × 10^4 × 144 ≈ 4.3 × 10^6 starting walks, and on a board full of a with words like aaaaaaaaab each walk explores thousands of paths.

From brute force to the idea

  1. Find the waste. Words such as oath, oat and oats all start with the same walk o, a, t, but the brute force repeats it for each word.
  2. Put the words in a trie. build_trie stores each word along its letters and puts the whole word under the "$" key at its end, so a match can be reported without rebuilding the string.
  3. Walk the board and the trie together. dfs(r, c, node) steps into a cell only if its letter is a child of the current trie node. If not, no word continues this way: a dead end.
  4. Report and remove. When the new node has "$", a word is complete. node.pop("$") appends it and deletes the marker, so the same word is never reported twice even if the board spells it along several paths.
  5. Mark cells in use. Set the cell to "#" before exploring neighbours (nbrs yields the in-grid ones) and restore the letter afterwards. "#" is never a trie key, so a used cell cannot be stepped into again in the same path.
  6. Start everywhere. all_cells lists every position, and each starts a walk from the root.

This is the key idea: one DFS per start cell follows the trie, so all words with a shared prefix share the work, and a path stops as soon as it is no word's prefix.

The key idea

Build a trie of all words and run one backtracking search over the grid, pruned by the trie.

Python solution

def find_words(board, words):
    trie = build_trie(words)  # "$" = end
    found = []
    def dfs(r, c, node):
        ch = board[r][c]
        if ch not in node:
            return  # dead end
        node = node[ch]
        if "$" in node:
            found.append(node.pop("$"))
        board[r][c] = "#"          # in use
        for nr, nc in nbrs(board, r, c):
            if board[nr][nc] != "#":
                dfs(nr, nc, node)
        board[r][c] = ch
    for r, c in all_cells(board):
        dfs(r, c, trie)
    return found

def build_trie(words):
    root = {}
    for w in words:
        node = root
        for ch in w:
            node = node.setdefault(ch, {})
        node["$"] = w
    return root

def all_cells(g):
    return [(r, c) for r in range(len(g))
            for c in range(len(g[0]))]

def nbrs(g, r, c):  # in-grid neighbours
    R, C = len(g), len(g[0])
    for nr, nc in ((r+1, c), (r-1, c),
                   (r, c+1), (r, c-1)):
        if 0 <= nr < R and 0 <= nc < C:
            yield nr, nc

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

Let L be the longest word length (at most 10) and S the total letters in all words.

ApproachTimeSpace
Brute forceO(W · R · C · 4 · 3^(L − 1)) for W words: a full grid search per wordO(L) recursion depth
Trie + DFS (shown code)O(S) to build the trie, plus O(R · C · 4 · 3^(L − 1)) for the walks, independent of WO(S) for the trie, O(L) recursion depth

Edge cases

  • The example: returns ["oath", "eat"]. The order is the order of discovery, not the order of words.
  • Spelled more than once (board a a, words a): returned once, because the marker is popped.
  • Reusing a cell (board a b, word aba): not found, since the a is marked "#" while in use.
  • A 1 × 1 board: a is found, aa is not.
  • The board is changed during the search but every cell is restored, so the caller's board is the same afterwards.
  • No pruning of finished branches: after oath is found, its now-empty trie nodes stay, so later walks still step through o, a, t, h. Deleting empty child nodes on the way back is a common speed-up; the answer is correct without it.

Common mistakes

  • Appending node["$"] without popping it. The board a a with word a then returns ["a", "a"].
  • Forgetting to restore board[r][c] = ch, so later walks see "#" and miss words.
  • Running a separate grid search for each word, which repeats the shared-prefix walks.
Your turn: diagonal moves

Now a word may also continue diagonally, so each cell has up to 8 neighbours. Cells still cannot be reused within a word. Describe your approach, then write it if you like.

Compare with our answer

Nothing about the trie changes. Only the neighbour generator does: yield all eight offsets instead of four. The "#" marking still stops a path from reusing a cell.

DIRS8 = [(dr, dc) for dr in (-1, 0, 1) for dc in (-1, 0, 1) if dr or dc]

def nbrs(g, r, c):  # in-grid neighbours, diagonals included
    R, C = len(g), len(g[0])
    for dr, dc in DIRS8:
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C:
            yield nr, nc

Replace the shown nbrs with this. Each step now has up to 7 unused directions instead of 3, so the worst case grows to O(R · C · 8 · 7^(L − 1)), but the trie still cuts most paths short.

A strong answer mentions: that only the neighbour list changes, that cells must still be marked in use, and how the branching factor grows.

Check what stuck

1. A Boggle app must find which of 200,000 dictionary words appear on a 4 × 4 board. Which approach fits best?

2. Why does the shown code's walk cost not grow with the number of words?

3. A learner writes found.append(node["$"]) instead of popping the marker. Which call now returns a wrong result?

Score 60% or more and the lesson is marked complete.