When is a path an answer?

Store stone, stop, sun.

How would a hash set, a sorted list, and a trie answer exact membership or prefix "sto"?

Why does reaching sto fail to prove that sto was inserted?

1 / 6

Implement Trie (Prefix Tree) — predict before coding

A path records a prefix; an end marker records membership of a complete word. Keeping those two facts separate makes insertion, exact search, and prefix search small operations with different stopping conditions.

Decision: After Insert("apple"), what are Search("app"), StartsWith("app"), and Search("apple")? What changes after Insert("app")?

Presenter notes

Model answer: They are false, true, and true. Inserting app marks the existing app node terminal, so Search("app") becomes true without altering apple or allocating another shared prefix.

Correctness argument: After consuming i bytes, the current node represents exactly the length-i prefix. Insertion follows existing edges or creates the missing next edge, preserving that path invariant and marking only the final node terminal. It never removes edges or terminals, so earlier words remain present. Search fails exactly when a required edge is absent; after all bytes, it succeeds only if the terminal marker is set. StartsWith uses the same walk but does not require a terminal marker. Thus inserting a longer word implies its prefixes have paths, not that they were inserted as words.

Debugging prompt: Test a word that is a prefix of another in both insertion orders, repeated insertion, and two independent constructors. A zero-value Trie is not the initialized object; use Constructor.

2 / 6

Design Add and Search Words Data Structure — predict before coding

A dot means exactly one character, not any-length text. Searching is a DFS over (trie node, pattern position); a literal has one possible edge and a wildcard may branch.

Decision: After adding bad, dad, and mad, which of .ad, b.., .., and b... match? Why is dot not equivalent to a regular-expression star?

Presenter notes

Model answer: .ad and b.. match. .. is too short and b... too long. Each dot consumes exactly one trie edge; it cannot match zero or several characters.

Correctness argument: The search state represents words whose prefix matches exactly the consumed pattern prefix. A literal transition preserves this fact only through its matching child. A dot transition explores every existing one-character child, covering all and only possibilities for that position. At the end of the pattern, accepting only a terminal node enforces exact length and complete-word membership. Induction on the remaining pattern length proves the returned disjunction is true exactly when an inserted word matches. Search reads but does not consume terminal markers, so repeated queries remain consistent.

Debugging prompt: At pattern exhaustion, check end rather than merely a non-nil node. Avoid creating children during search. Test a wildcard before a missing suffix and repeated identical searches.

3 / 6

Word Search II — predict before coding

Combine two pruning rules: a board path cannot reuse cells, and its letters must remain a dictionary prefix. The trie shares work among words; it does not replace the board visited state.

Decision: With dictionary ["a","ab"] and adjacent board cells a,b, why may you clear the terminal word at a but not delete the entire a branch?

Presenter notes

Model answer: Clearing the terminal suppresses another copy of a. Deleting the branch also destroys the path to ab, incorrectly pruning an undiscovered longer word. Board marks must also be restored so another search can reuse cells on a different path.

Correctness argument: At each DFS entry, the trie node represents the letters chosen before the current cell and the temporary board marks represent exactly the cells on that current path. Following the cell letter succeeds only for a dictionary prefix. Marking the cell before recursion prevents reuse; restoring it afterward makes it available to different paths and different starting cells. Reaching a terminal proves one dictionary word is formed by a legal path. Clearing only its stored word suppresses duplicate output while retaining children needed for longer words. Every legal matching path is explored until its terminal, so all distinct present words are returned.

Debugging prompt: Test shared prefixes, a word found by several paths, and a tempting path that reuses one cell. Compare answers as a set while rejecting duplicate returned words. Verify the board is restored after the call.

4 / 6

Replace Words — predict before coding

The shortest matching root is the first terminal encountered while walking a sentence word. Unlike longest-prefix routing, continuing past that terminal would solve the wrong problem.

Decision: With roots ["cat","c","cattle"], what replaces "cattle"? Does dictionary insertion order affect the result?

Presenter notes

Model answer: The result is c. Search stops after the first character because that node is terminal. All dictionary roots inhabit the same trie, so insertion order does not change the shortest terminal on the path.

Correctness argument: After i bytes, the trie walk has checked every shorter prefix of the word. If the current node is terminal, that prefix is a dictionary root and no earlier prefix was terminal, so it is the shortest possible replacement. If a required child is absent, no dictionary root can extend the consumed prefix, and no earlier root was found; the original word must remain unchanged. Applying this independent rule to each word preserves word order. Under the single-space sentence contract, Fields followed by Join preserves the specified separators exactly.

Debugging prompt: Do not overwrite the answer with a later, longer terminal. Test an unchanged word and two roots nested within each other. The current tokenizer is not a whitespace-preserving general text editor.

5 / 6

Change one stopping rule

Roots are ["an","ant"]. Compare shortest-root and longest-root replacement of "antler".

Then explain why finding word "an" during board search cannot use either replacement rule blindly.

6 / 6