Word Search II (LeetCode 212)

The problem

You get a grid of letters and a list of words. Return every word that can be formed by a path of adjacent cells (up, down, left, right), using each cell at most once per word.

Board:            Words: ["oath", "pea", "eat", "rain"]
o a a n
e t a e
i h k r
i f l v

Output: ["eat", "oath"]

oath starts at the top-left o, steps right to a, then down the second column through t and h. eat runs right to left along the second row. pea and rain cannot be traced.

How to think about it

Start with brute force. Run Word Search once per word: from every cell, backtrack to see if that word can be spelt. For W words on an R×C grid, that is W full grid searches, each up to O(R·C·4^L). With thousands of words, you repeat the same grid paths over and over.

The key insight: search for all words at once, guided by a trie. Put every word into a trie. Then run one backtracking DFS from each cell, carrying a pointer into the trie. Step to a neighbour only if its letter is a child of the current trie node. The trie therefore prunes the search: the moment a path spells a prefix that no word has, the DFS stops. Shared prefixes (oa..., oat...) are explored once, for every word that uses them.

Finding a word. Store the full word at its end node ('$'). When the DFS reaches a node with '$', record the word and delete the marker, so the same word is not reported again from another path.

Which pattern is this? Trie plus backtracking. The tell is “find many words in a grid”. Backtracking needs one more trick: mark a cell as used ('#') before recursing and restore it afterwards.

Approach

1. Build a trie from the words, storing each word under '$' at its end node.
2. For every cell, call dfs(r, c, root).
3. In dfs, if the cell’s letter is not a child of node, return. Otherwise move to that child nxt.
4. If nxt has '$', add the word to the result and remove the marker.
5. Mark the cell '#', recurse into the four in-bounds, unused neighbours with nxt, then restore the letter.
6. Return the found words, sorted.

Solution

def findWords(board, words):
    root = {}
    for w in words:
        n = root
        for c in w: n = n.setdefault(c, {})
        n['$'] = w
    R, C = len(board), len(board[0]); res = []
    def dfs(r, c, node):
        ch = board[r][c]
        if ch not in node: return                       # no word has this prefix: prune
        nxt = node[ch]
        if '$' in nxt: res.append(nxt['$']); del nxt['$']   # found; avoid duplicates
        board[r][c] = '#'                               # mark as used on this path
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and board[nr][nc] != '#': dfs(nr, nc, nxt)
        board[r][c] = ch                                # backtrack
    for r in range(R):
        for c in range(C): dfs(r, c, root)
    return sorted(res)
# findWords([["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]],
#           ["oath","pea","eat","rain"]) -> ["eat","oath"]

Dry run

The trie’s root has children o, p, e, r. Only four cells start a search that gets past the first letter check:

Words are found in the order oath, eat; after sorting, the answer is ["eat", "oath"]. Every other cell fails at the first check because its letter is not a trie root child. That is the pruning at work.

Complexity

• Time: O(R·C·4·3^(L−1)) in the worst case, where L is the longest word. Each start cell explores at most 4 directions, then at most 3 (you cannot go back). In practice the trie cuts this down sharply, and the trie build costs O(total characters of the words).
• Space: O(total characters) for the trie, plus O(L) recursion depth.

Edge cases and pitfalls

• Same word found twice from different paths: deleting '$' prevents duplicates. Duplicate words in the input (["a", "a"]) also collapse to one result.
• Reusing a cell ("aaa" on a 1×2 board of as) must fail. The '#' mark blocks it.
• Forgetting to restore the letter after the DFS corrupts the board for later searches. The board is unchanged after the call.
• One search per word is the common wrong approach: correct, but it times out on large word lists.
• Further pruning: delete trie nodes that become empty after a word is found, so dead branches are never walked again.

Related problems

• Word Search (LeetCode 79): the single-word backtracking this generalises.
• Design Add and Search Words Data Structure (LeetCode 211): another DFS that walks a trie.
• Number of Islands (LeetCode 200): the same four-direction grid DFS, without backtracking.