-
Notifications
You must be signed in to change notification settings - Fork 0
093 — Word Search II
LeetCode 212 · Hard. Given an m x n board of characters and a list of words, return all words from the list that can be formed by a path of adjacent cells (horizontally or vertically neighboring, no cell reused within a single word).
This is Word Search I turned up to a harder setting: instead of hunting for one word, you're hunting for potentially thousands at once. The naive move is "just run the single-word search once per word" — but that means re-walking the same board, re-exploring the same early cells, over and over, once per word, even when many words share the same first few letters ("oath" and "oat" both start by walking the exact same o → a → t path). The fix mirrors chapters 91 and 92: stop treating the word list as independent strings. Build a trie out of all of them first, so the search explores the board once, and at every cell checks "which of my still-possible words could this next letter continue" — pruning any path the moment it stops matching any word at all.
"Find all words from a list that appear in a grid via adjacent-cell paths" — the combination of "many words to find" + "grid adjacency" is the cue that this isn't just Word Search I repeated; it's Word Search I's DFS-over-grid merged with a trie, so the board walk and the word matching happen together in one pass instead of one full board search per word.
Run an independent Word Search I style DFS/backtracking search for each word in the list, starting from every cell, marking visited cells along the current path.
func findWordsBruteForce(_ board: [[Character]], _ words: [String]) -> [String] {
var board = board
let rows = board.count, cols = board[0].count
var found: [String] = []
func exists(_ word: String) -> Bool {
let chars = Array(word)
func dfs(_ r: Int, _ c: Int, _ i: Int) -> Bool {
if i == chars.count { return true }
if r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != chars[i] {
return false
}
let temp = board[r][c]
board[r][c] = "#"
let result = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1)
|| dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1)
board[r][c] = temp
return result
}
for r in 0..<rows {
for c in 0..<cols {
if dfs(r, c, 0) { return true }
}
}
return false
}
for word in words where exists(word) {
found.append(word)
}
return found
}
// smoke test
let board1: [[Character]] = [
["o","a","a","n"],
["e","t","a","e"],
["i","h","k","r"],
["i","f","l","v"]
]
print(Set(findWordsBruteForce(board1, ["oath", "pea", "eat", "rain"])))
// {"eat", "oath"} — "pea" and "rain" aren't reachable via adjacent cellsBig-O: O(words · rows · cols · 4^L), where L is the max word length — each word triggers its own full board scan, and each scan can branch up to 4 ways at every one of L steps. Every word pays for the same early board exploration independently.
Build a trie of all the words up front (each end-of-word node stores the actual word string). Then do a single DFS pass starting from every board cell, following trie edges instead of a fixed target string: at each cell, only descend into the trie child matching that cell's letter — any cell whose letter has no matching trie child ends the search immediately, which is the pruning brute force can't get for free. When a trie node marked with a word is reached, record it and clear the marker so it's never reported twice.
final class WordTrieNode {
var children: [Character: WordTrieNode] = [:]
var word: String? = nil // set only on nodes where a full word ends
}
func findWords(_ board: [[Character]], _ words: [String]) -> [String] {
let root = WordTrieNode()
for word in words {
var node = root
for char in word {
if let next = node.children[char] {
node = next
} else {
let next = WordTrieNode()
node.children[char] = next
node = next
}
}
node.word = word
}
var board = board
let rows = board.count, cols = board[0].count
var result: [String] = []
func dfs(_ r: Int, _ c: Int, _ node: WordTrieNode) {
guard r >= 0, r < rows, c >= 0, c < cols else { return }
let char = board[r][c]
guard char != "#", let next = node.children[char] else { return }
if let found = next.word {
result.append(found)
next.word = nil // avoid reporting the same word again via another path
}
board[r][c] = "#" // mark visited for this path
dfs(r + 1, c, next)
dfs(r - 1, c, next)
dfs(r, c + 1, next)
dfs(r, c - 1, next)
board[r][c] = char // backtrack
// prune: if this trie branch has no words left under it, drop it
// from the parent so future DFS calls stop early at this letter
if next.children.isEmpty {
node.children.removeValue(forKey: char)
}
}
for r in 0..<rows {
for c in 0..<cols {
dfs(r, c, root)
}
}
return result
}
// smoke test — same board as brute force
print(Set(findWords(board1, ["oath", "pea", "eat", "rain"])))
// {"eat", "oath"}
// duplicate-avoidance check: a one-letter word reachable from two cells
// must still be reported only once
let board2: [[Character]] = [["a", "a"]]
print(findWords(board2, ["a"])) // ["a"] — not ["a", "a"]Big-O: O(rows · cols · 4^L) for the board walk (L = max word length), plus O(total characters across all words) to build the trie. The board is explored once total, not once per word — shared prefixes across words are walked exactly once, and the pruning step (removing exhausted trie branches) keeps later DFS calls from wasting time re-descending into parts of the trie that have nothing left to find.
The brute force's real waste is redundant board exploration: if "oath" and "oat" are both in the list, a per-word search walks the exact same o → a → t cells twice, from scratch, once for each word. The optimal version merges the word list into a trie first so that shared prefixes correspond to shared DFS branches — walking o → a → t once serves every word that starts that way. Two more details make it fast in practice rather than just "asymptotically less redundant": storing the matched word directly on its trie node (rather than reconstructing it from the path) makes reporting a match O(1), and deleting exhausted branches (next.children.isEmpty) means a dead end is only ever explored once — later DFS calls starting from other cells won't waste time descending into a subtree that's already been proven empty.
- Tries — the trie built from the word list is what turns "search separately for each word" into "search the board once."
- DFS and Backtracking — the board walk marks a cell visited, recurses into its neighbors, and unmarks it on the way back out, exactly like Word Search I's single-word backtracking search.
- Matrix Traversal — the four-directional adjacency walk over the 2D board, with bounds checks at every step.
Word Search II is Word Search I run for every word at once — build a trie of the whole word list first, then walk the board a single time, letting shared prefixes share the same walk instead of repeating it.
Using the board [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]] and words ["oath", "oat"], trace the trie built from those two words — which node has word = "oat" and which has word = "oath"? Then trace the DFS starting at (0,0) ("o"): at what point does the search record "oat", and does it need to restart from (0,0) to then find "oath", or does the same in-progress DFS call continue on to find it too? Explain why the next.children.removeValue pruning step is safe to do after recursing into all four neighbors, but would be wrong if done before.
⬅️ Previous: Design Add and Search Words Data Structure · Next: Kth Largest Element in a Stream ➡️