Core Insight Store shared prefixes once so every character chooses the next edge in constant time.
Common Pitfall Keep an explicit end-of-word marker; reaching a node alone does not mean a word ends there.
Description
Implement a trie with insert, search, and startsWith methods.
Constraints
- Time Complexity:
O(n) - Space Complexity:
O(n)
Tags
hash-mapstringdesigntrie
Implementation Plan Translate the invariant into these small, testable moves.
- Start at the root.
- Create or follow the edge for each character.
- Mark complete words explicitly.
- Use the same traversal rule for lookup.
class TrieNode:
def __init__(self):
self.children = {}
self.endOfWord = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
cur = self.root
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.endOfWord = True
def search(self, word: str) -> bool:
cur = self.root
for c in word:
if c not in cur.children:
return False
cur = cur.children[c]
return cur.endOfWord
def startsWith(self, prefix: str) -> bool:
cur = self.root
for c in prefix:
if c not in cur.children:
return False
cur = cur.children[c]
return True