The problem
Build a trie (pronounced “try”), a tree for storing words. Support insert(word); search(word), which says whether that exact word was inserted; and startsWith(prefix), which says whether any inserted word begins with prefix.
Examples
- Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
- Output
[null, null, true, false, true, null, true]
Constraints
- 1 ≤ word.length, prefix.length ≤ 2000
- Only lowercase English letters.
- At most 3 × 10⁴ calls in total.
The idea
Each node of a trie has up to 26 children, one per letter. A word is a path from the root: cat goes root → c → a → t. Words with a common beginning share its path — car and cat share root → c → a.
Insert walks the path, creating any missing nodes, and marks the last node as the end of a word. Search and startsWith both walk the path and fail if a letter is missing; the difference is that search also needs the end mark — app is a prefix of apple but only a word if it was inserted itself.
- Time
- O(L) per call — one step per letter
- Space
- O(total letters inserted) — at most one node each
Solution · every language run against every case
class Trie: def __init__(self): self.root = {} # each node: letter -> child node; "$" marks the end of a word def insert(self, word: str) -> None: node = self.root for c in word: node = node.setdefault(c, {}) node["$"] = True def _walk(self, s: str): # the node reached by spelling s, or None node = self.root for c in s: if c not in node: return None node = node[c] return node def search(self, word: str) -> bool: node = self._walk(word) return node is not None and "$" in node def startsWith(self, prefix: str) -> bool: return self._walk(prefix) is not None