DiffPush Tier Tries · Theory O(L) per operation · O(total inserted characters)
An airport builds a type-ahead directory for gate labels: staff type a label fragment and the kiosk must confirm whether a full label exists, or whether any label begins with that fragment. The directory is rebuilt per shift, so it needs fast insert, exact lookup, and prefix lookup — all sharing one letter-by-letter structure.
Input: A list of operations, each either ["insert", word], ["search", word], or ["startsWith", prefix]. The first operation is always ["Trie"].
Output: Return one entry per search or startsWith operation: true or false. insert yields null.
1 <= number of operations <= 3 * 10^41 <= len(word), len(prefix) <= 2000words and prefixes use lowercase English lettersall inserted words are distinctInput: {"ops":[["Trie"],["insert","apple"],["search","apple"],["search","app"],["startsWith","app"],["insert","app"],["search","app"]]}
Output: [null,null,true,false,true,null,true]
"apple" is stored exactly; "app" only becomes a full label after its own insert.
Input: {"ops":[["Trie"],["insert","gate"],["startsWith","ga"],["search","ga"],["startsWith","gb"]]}
Output: [null,null,true,false,false]
The prefix "ga" matches, but "ga" alone is not a stored label.