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
Design a data structure supporting addWord and search with wildcards.
Constraints
- Time Complexity:
O(n) - Space Complexity:
O(n)
Tags
stringdepth-first-searchdesigntrie
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.word = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(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.word = True
def search(self, word: str) -> bool:
def dfs(j, root):
cur = root
for i in range(j, len(word)):
c = word[i]
if c == ".":
for child in cur.children.values():
if dfs(i + 1, child):
return True
return False
else:
if c not in cur.children:
return False
cur = cur.children[c]
return cur.word
return dfs(0, self.root)