Word Search II
Problem
Given an m × n board of characters and a list of strings words, return all words that can be formed on the board.
Each word must be built from letters of sequentially adjacent cells (horizontally or vertically), and a cell may not be used twice in one word.
Example 1
- Input
board = [["o","a","a","n"], ["e","t","a","e"], ["i","h","k","r"], ["i","f","l","v"]], words = ["oath", "pea", "eat", "rain"]- Output
["eat", "oath"]
Example 2
- Input
board = [["a","b"], ["c","d"]], words = ["abcb"]- Output
[]
Constraints
- 1 ≤ m, n ≤ 12
- 1 ≤ words.length ≤ 3 × 10⁴, 1 ≤ words[i].length ≤ 10
Explanation
Running Word Search once per word repeats the same grid walks thousands of times.
Put all words in a trie instead and walk the grid once from each cell, following the trie as you go. A path that is not a prefix of any word stops immediately. When you reach a node that ends a word, record it.
Approach 1 · Naive
Word Search for each word
- Time O(W · m · n · 3^L)
- Space O(L) recursion
Run the single-word grid DFS for every word in the list.
- For each word, try every starting cell with a backtracking DFS.
- Collect the words that are found.
import java.util.*;
class Solution {
public List<String> findWords(char[][] board, String[] words) {
List<String> result = new ArrayList<>();
for (String word : words) {
if (exists(board, word)) {
result.add(word);
}
}
return result;
}
private boolean exists(char[][] board, String word) {
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[0].length; c++) {
if (dfs(board, word, r, c, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int r, int c, int i) {
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] != word.charAt(i)) {
return false;
}
if (i == word.length() - 1) {
return true;
}
char saved = board[r][c];
board[r][c] = '#';
boolean found = dfs(board, word, r + 1, c, i + 1) || dfs(board, word, r - 1, c, i + 1)
|| dfs(board, word, r, c + 1, i + 1) || dfs(board, word, r, c - 1, i + 1);
board[r][c] = saved;
return found;
}
}class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
m, n = len(board), len(board[0])
def dfs(word, r, c, i):
if not (0 <= r < m and 0 <= c < n) or board[r][c] != word[i]:
return False
if i == len(word) - 1:
return True
saved, board[r][c] = board[r][c], "#"
found = (dfs(word, r + 1, c, i + 1) or dfs(word, r - 1, c, i + 1)
or dfs(word, r, c + 1, i + 1) or dfs(word, r, c - 1, i + 1))
board[r][c] = saved
return found
return [w for w in words if any(dfs(w, r, c, 0) for r in range(m) for c in range(n))]Approach 2 · Optimal
Trie-guided DFS
- Time O(m · n · 3^L), shared across all words
- Space O(total characters in words)
Build a trie of all words, storing the full word at its last node. DFS from every cell, moving only along trie edges, and collect words as their nodes are reached.
- Insert every word into a trie; the end node keeps the word.
- From each cell,
dfs(r, c, node): stop if the letter is not a child ofnode. - Move to the child; if it holds a word, add it and clear it (so it is reported once).
- Mark the cell, explore four neighbours, unmark.
import java.util.*;
class Solution {
private static class Node {
Node[] children = new Node[26];
String word;
}
public List<String> findWords(char[][] board, String[] words) {
Node root = new Node();
for (String w : words) {
Node node = root;
for (char c : w.toCharArray()) {
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new Node();
}
node = node.children[c - 'a'];
}
node.word = w;
}
List<String> result = new ArrayList<>();
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[0].length; c++) {
dfs(board, r, c, root, result);
}
}
return result;
}
private void dfs(char[][] board, int r, int c, Node parent, List<String> result) {
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] == '#') {
return;
}
char letter = board[r][c];
Node node = parent.children[letter - 'a'];
if (node == null) {
return;
}
if (node.word != null) {
result.add(node.word);
node.word = null;
}
board[r][c] = '#';
dfs(board, r + 1, c, node, result);
dfs(board, r - 1, c, node, result);
dfs(board, r, c + 1, node, result);
dfs(board, r, c - 1, node, result);
board[r][c] = letter;
}
}class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = {}
for w in words:
node = root
for c in w:
node = node.setdefault(c, {})
node["$"] = w # the word that ends here
m, n = len(board), len(board[0])
result = []
def dfs(r, c, parent):
if not (0 <= r < m and 0 <= c < n):
return
letter = board[r][c]
node = parent.get(letter)
if node is None:
return
if "$" in node:
result.append(node.pop("$"))
board[r][c] = "#"
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
dfs(r + dr, c + dc, node)
board[r][c] = letter
for r in range(m):
for c in range(n):
dfs(r, c, root)
return resultComplexity compared
| Approach | Time | Space |
|---|---|---|
| Naive Word Search for each word | O(W · m · n · 3^L) | O(L) recursion |
| Optimal Trie-guided DFS | O(m · n · 3^L), shared across all words | O(total characters in words) |
Key takeaways
- Storing the word on its end node avoids rebuilding strings during the DFS.
- Clearing the word after finding it prevents duplicates; pruning empty trie branches as you go makes it faster still.
Your notes
Saved in this browser as you type.
Solved it on your own?
Mark it done to track your progress, or star it to come back before an interview.