Week 10 · Tries

Word Search II

Solve Word Search II by recognizing the Tries pattern and turning the prompt into a small invariant before coding.

Hard Tries Week 10 Practice runner

Frame the problem

Implement find_words with the exact signature used by the interactive runner.
Use the visible tests to confirm the input and output shape before reading the final solution.
Treat challenge tests as edge-case pressure: empty inputs, repeated values, boundary shapes, or impossible states.
State the invariant before code, then dry-run one passing case and one failing-looking case.

1. Reveal example inputs and outputs

Example 1

Input:

find_words([
  [
    "o",
    "a",
    "a",
    "n"
  ],
  [
    "e",
    "t",
    "a",
    "e"
  ],
  [
    "i",
    "h",
    "k",
    "r"
  ],
  [
    "i",
    "f",
    "l",
    "v"
  ]
], [
  "oath",
  "pea",
  "eat",
  "rain"
])

Output:

[
  "eat",
  "oath"
]

2. Brute force first

What direct brute force would be correct for a tiny input? Name the exact repeated work that the target pattern removes.

3. Reveal the insight ladder

Map the prompt to the Tries pattern instead of starting from syntax.
Build a trie of words, then DFS from each board cell.
Do not reuse a board cell in one word path.
Only reveal the final code after you can explain why each state update is safe.

4. Dry run before code

word-search-ii-basic: input [[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]],["oath","pea","eat","rain"]] should produce ["eat","oath"]. Hint to check your state: Build a trie of words, then DFS from each board cell.
word-search-ii-none: input [[["a","b"],["c","d"]],["abcb"]] should produce []. Hint to check your state: Do not reuse a board cell in one word path.

5. Reveal final Python solution

def find_words(board: list[list[str]], words: list[str]) -> list[str]:
    trie: dict[str, Any] = {}
    for word in words:
        node = trie
        for char in word:
            node = node.setdefault(char, {})
        node["$"] = word

    rows, cols = len(board), len(board[0])
    found: set[str] = set()

    def dfs(row: int, col: int, node: dict[str, Any]) -> None:
        if row < 0 or row == rows or col < 0 or col == cols:
            return
        char = board[row][col]
        if char == "#" or char not in node:
            return
        next_node = node[char]
        if "$" in next_node:
            found.add(next_node["$"])
        board[row][col] = "#"
        dfs(row + 1, col, next_node)
        dfs(row - 1, col, next_node)
        dfs(row, col + 1, next_node)
        dfs(row, col - 1, next_node)
        board[row][col] = char

    for row in range(rows):
        for col in range(cols):
            dfs(row, col, trie)
    return sorted(found)

Complexity: Derive the exact bounds from find_words: count how often each input item is visited and the maximum size of the main state structure.

Interview narration

I will first describe the invariant in plain language.
Then I will explain what data structure carries that invariant across the traversal, loop, recursion, or DP transition.
Finally I will walk one edge case before writing the optimized version.

Common traps

Solving only the visible example instead of the invariant.
Forgetting empty input, singleton input, duplicate values, or impossible-state cases.
Revealing the solution before doing a dry run from the starter signature.

Follow-up drills

1. How do you turn this into a timed interview answer?

Start with the invariant, give the brute force in one sentence, name the optimized state, code the core loop or recursion, and run one visible test aloud before mentioning complexity.

2. How do you scale the same pattern to a larger input?

Track which state grows with the input: hash maps and sets grow with distinct values, queues grow with frontier width, recursion grows with depth, heaps grow with active candidates, and DP tables grow with state count.

3. What should you practice from blank tomorrow?

Rewrite find_words without looking at the solution, then compare only the invariant and state updates before checking syntax.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.