Trie — How the Pattern Works
A Trie (Prefix Tree) is a multi-way rooted tree that stores strings or digit sequences one character per edge, maintaining the invariant that every node at depth d uniquely represents the shared d-character prefix of all keys in its subtree. By consolidating shared prefixes onto a single root-to-node path and marking complete words with terminal flags ("$"), a trie answers exact-match and prefix queries in O(L) time proportional only to the query length L rather than dictionary size n—reducing O(n * L) linear scans and O(n log n) comparison sorts. Augmenting nodes with precomputed subtree metadata (such as running sums, earliest indices, shortest-word ties, or lexicographical subtree counts) further turns grid searches, suffix queries, and huge lexicographical rankings into fast prefix walks.
- A dictionary of many strings is queried repeatedly for exact membership, prefix existence (
startsWith), longest common prefixes, or shortest root replacements (Replace Words). - Characters arrive incrementally or outputs must be produced in lexicographical order—such as typeahead autocomplete (
Search Suggestions System), frequency-bucketed alphabetical tie-breaking (Top K Frequent Words), or1..ndictionary ordering. - Multiple words or wildcard patterns are matched simultaneously against a 2D character board (
Word Search II), a text string (Index Pairs of a String), or.wildcards, where pruning dead prefixes eliminates exponential branches. - Queries compare word suffixes or mirrored concatenations (
Longest Common Suffix Queries,Palindrome Pairs), which map directly to prefix walks over a trie of reversed words.
- Omitting the terminal marker (
"$") makes prefixes indistinguishable from complete words, causingsearch("ca")to falsely returnTrueafter inserting"cat". - Breaking at the first
"$"marker when all matches are required—correct for shortest-rootReplace Words, but a bug inIndex Pairs of a StringandWord Search IIwhere longer words like"aba"or"oat"extend past shorter matches. - Iterating child keys without excluding metadata keys (
k != "$"ork != "total"), which attempts to traverse a boolean, string, or integer payload as a child dictionary and raisesTypeError. - Adding raw values instead of net deltas (
diff = val - old_val) when updating existing keys in prefix-sum tries (Map Sum Pairs), double-counting the old key value on every ancestor node.
def build_trie(words):
root = {}
for word in words:
cur = root
for c in word:
cur = cur.setdefault(c, {})
cur["$"] = word
return rootdef collect_sorted(node, limit, out):
for key in sorted(node):
if len(out) == limit:
return out
if key == "$":
out.append(node["$"])
else:
collect_sorted(node[key], limit, out)
return outdef wildcard_search(node, pattern, i=0):
if i == len(pattern):
return "$" in node
c = pattern[i]
if c == ".":
return any(wildcard_search(node[k], pattern, i + 1)
for k in node if k != "$")
return c in node and wildcard_search(node[c], pattern, i + 1)