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.

1# The root's children, for a trie holding bad, dad, and mad.2children = {"b": "...", "d": "...", "m": "..."}3 4for ch in (".", "b", "p"):5    if ch == ".":6        followed = sorted(children)7    elif ch in children:8        followed = [ch]9    else:10        followed = []11    print(repr(ch), "at the root follows", followed, "->", len(followed), "way(s)")

A literal follows one edge or none. A wildcard follows every edge there is, which is what turns the walk into a search.

Quick check· 5 min

Where does the flag get checked?

In the wildcard search, where must the end-of-word flag be checked?

Only in the base case, when the pattern is exhaustedAt every node visited, so partial matches are caught earlyOnly when the current pattern character is a wildcardNowhere; reaching the end of the pattern is itself a match

Problem· 28 min

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.

1# The root's children, for a trie holding bad, dad, and mad.2children = {"b": "...", "d": "...", "m": "..."}3 4for ch in (".", "b", "p"):5 if ch == ".":6 followed = sorted(children)7 elif ch in children:8 followed = [ch]9 else:10 followed = []11 print(repr(ch), "at the root follows", followed, "->", len(followed), "way(s)")