Word Search II
LeetCode 212 • Hard • Tries
Input: board + words → find all words. Trie build + DFS on board. Example: board 2×2, words=["ab","ba"] → ["ab","ba"].
TimeO(m·n·4^L)
SpaceO(W)
path: —
found: —
Ready
Press Play. Build trie from words. DFS from each cell. When trie node is word end, add to result.
Practice until you don't need to look. Trie + DFS. Remove word from trie when found (or mark visited).
PATTERN ▸ Build trie, DFS from each cell O(m·n·4^L) · O(W)
① BUILD TRIE
for w in words: trie.insert(w)
② DFS HELPER
def dfs(r,c,node,path): if node.is_word: result.add(path)
for dr,dc in dirs: explore neighbor if char in node.children
③ ENUMERATE STARTS
for r,c: if board[r][c] in trie.root: dfs(r,c,trie.root[char],char)
④ RETURN
return list(result)
your implementation