Store the shared beginning once
Picture
The words car, cart, and cat share a beginning. A trie stores that common prefix as one path, then branches where the words diverge. A node means “this prefix exists”; a separate marker says whether the prefix itself is a complete word.
Predict
After inserting only cart, does reaching the node for car mean car is a stored word?
Reveal the reasoning
No. It is a stored prefix. Without an end-of-word marker, the trie cannot distinguish complete words from intermediate prefixes.
Go deeper: separate structure from terminal meaning
Use dictionary children and None as an end marker; input words are strings, so their character keys cannot equal None.
def insert(root, word):
node = root
for char in word:
node = node.setdefault(char, {})
node[None] = True
def follow(root, text):
node = root
for char in text:
if char not in node:
return None
node = node[char]
return node
trie = {}
insert(trie, "cart")
assert follow(trie, "car") is not None
assert None not in follow(trie, "car")
insert(trie, "car")
assert None in follow(trie, "car")
assert follow(trie, "dog") is None
root → c → a → r [word]
└→ t [word]
Insertion and prefix traversal take expected O(L) dictionary operations for length L. For total inserted character count S, the number of nodes is at most S+1. Python dictionaries per node can have substantial overhead, so asymptotic bounds do not guarantee a compact representation.
Recognition signal: many queries need prefix structure or must abandon candidate words as soon as a prefix becomes impossible. For exact membership alone, a set of words is often sufficient. Listing autocomplete results also costs at least the size of the reported output.
Analogy limit: a trie shares beginnings, not arbitrary suffixes or equivalent future computations. The same letter under two different prefixes usually represents two different nodes.
Change one rule
Searches are case-insensitive. Where should normalization happen?
Check the variation
Use one explicit normalization rule for both insertion and lookup, and decide how original spellings are retained for output. Normalizing only one side changes which prefixes can match.
Connect
Trie search combines prefix storage with branching exploration. DP shares equivalent remaining questions; comparing these two kinds of sharing prevents treating every merged structure as DP.