Problem 62 · Strings & Tries

Word Search II

HardClassic DSA & systems

01Problem

Given an m x n board of letters and a list of words, return all words that can be formed by sequentially adjacent (4-directional) cells, using each cell at most once per word.

02Key insight

Build a trie of the words and run one DFS per cell that walks the trie in lockstep, so all words share prefix work; prune leaf nodes once their word is found to avoid re-exploring dead branches.

03Solution

solution.pypython30 lines

def find_words(board: list[list[str]], words: list[str]) -> list[str]:
    root: dict = {}
    for w in words:
        node = root
        for ch in w:
            node = node.setdefault(ch, {})
        node["$"] = w  # terminal marker stores the word itself

    rows, cols = len(board), len(board[0]) if board else 0
    found: list[str] = []

    def dfs(r: int, c: int, parent: dict) -> None:
        ch = board[r][c]
        node = parent[ch]
        if "$" in node:
            found.append(node.pop("$"))  # pop dedups results
        board[r][c] = "#"
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] in node:
                dfs(nr, nc, node)
        board[r][c] = ch
        if not node:
            parent.pop(ch)  # prune exhausted branch

    for r in range(rows):
        for c in range(cols):
            if board[r][c] in root:
                dfs(r, c, root)
    return found

Try it first.

TimeO(m*n*4*3^(L-1))

SpaceO(total chars in words)

tests.py · 3 passing

tests.pypython4 lines

b = [list("oaan"), list("etae"), list("ihkr"), list("iflv")]
assert sorted(find_words(b, ["oath", "pea", "eat", "rain"])) == ["eat", "oath"]
assert find_words([list("ab")], ["aba"]) == []
assert sorted(find_words([list("aa")], ["a", "aa", "a"])) == ["a", "aa"]

04Staff-level follow-up

How would you parallelize for a huge board? Partition starting cells across workers sharing a read-only trie; pruning then becomes per-worker, trading some redundant work for no locking.