Tries
When the search itself branches
A wildcard turns the walk into a recursion, because one position can go several ways.
Key idea
One character, many edges
The walk so far followed exactly one child per character, which is why a loop sufficed. A pattern containing a wildcard breaks that: at a wildcard position every child is a possible continuation.
As soon as one step can go several ways, the search is a recursion. This is Unit 10's structure appearing in a new place: a choice per level, explore each, and report whether any succeeded.
Why it works
The base case still checks the flag
Running out of pattern means the walk finished, and finishing is only a match if a word actually ends there. The flag check is the same one from the last lesson and it survives the move to recursion unchanged.
That is what separates a pattern from a prefix of one. On a trie holding only three-letter words, the pattern b. finishes after two characters on a node where nothing ends, so the honest answer is no even though the walk itself succeeded.
Tip
`any` gives short-circuiting for free
any over a generator stops at the first true result, so a matching branch ends the search immediately rather than exploring every child.
Building a list first with a comprehension in brackets would evaluate every branch before checking any of them. The distinction is invisible in small cases and matters on a wide trie.
Gotcha
Do not add words during a search
Iterating node.children.values() while something inserts into that dict raises RuntimeError: dictionary changed size during iteration.
In a design problem where both operations exist this is a real hazard if a search ever triggers an insert. Keeping the two operations strictly separate avoids it, and it is worth a sentence if an interviewer asks about concurrent use.
Cost
The cost of a wildcard
With no wildcards the search is O(L) as before. Each wildcard multiplies the work by the branching factor at that level, up to the alphabet size.
So a pattern of length L with w wildcards is O(L times a to the w) in the worst case, for alphabet size a. A pattern that is entirely wildcards degenerates to visiting every node of that depth, which is the same as scanning the whole dictionary. Saying that boundary out loud shows you know what the structure is and is not buying.
Where does the flag get checked?
In the wildcard search, where must the end-of-word flag be checked?
Add And Search Words Data Structure
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.