Problem. Implement a class with three operations:
insert(word): add the word;search(word): return True if the exact word was inserted;startsWith(prefix): return True if any inserted word starts with the prefix.
insert("apple")
search("apple") → True
search("app") → False ("app" is only a prefix so far)
startsWith("app") → True
insert("app")
search("app") → True
The difference between search("app") and startsWith("app") is the whole design: both walk the same path, but only search
asks whether a word ends at the last node. That one flag per node is what separates "a word" from "the beginning of a word".
ML context. A trie over a label set or vocabulary is how systems restrict outputs to valid strings: constrained decoding lets a language model generate only class names, product IDs or entity names that exist, by allowing at each step only the characters (or tokens) that are children of the current trie node (Change D). The same structure maps strings to token IDs in tokenizers.