Approach Summary
Insert all words into a Trie. DFS from each cell, following Trie edges. Mark found words to avoid duplicates. Prune dead Trie branches.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Prefix Trie with Multi-Word Grid DFS (Optimal) | O(M * N * 4^L) | O(Total characters in words) | Insert all words into a Trie and perform simultaneous grid DFS and Trie traversal. |
| 2 Approach 2: Standalone Word Search Backtracking for Each Word (Baseline) | O(W * M * N * 3^L) | O(L) | Executes standard DFS Word Search across the board for each word in the word list independently. |
Step 1: Baseline
Approach 1: Prefix Trie with Multi-Word Grid DFS (Optimal)
Time: O(M * N * 4^L)
Space: O(Total characters in words)
Indexing all target words into a Trie enables searching all dictionary candidates concurrently on the board. Unmatched paths prune immediately when a board letter does not exist as a Trie child.
Approach 1: Prefix Trie with Multi-Word Grid DFS (Optimal) Implementation
Approach 1: Prefix Trie with Multi-Word Grid DFS (Optimal)
class Solution {
class Node { Node[] c = new Node[26]; String word; }
public List<String> findWords(char[][] board, String[] words) {
Node root = new Node();
for (String w : words) {
Node n = root;
for (char ch : w.toCharArray()) {
if (n.c[ch - 'a'] == null) n.c[ch - 'a'] = new Node();
n = n.c[ch - 'a'];
}
n.word = w;
}
List<String> res = new ArrayList<>();
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[0].length; c++) {
if (root.c[board[r][c] - 'a'] != null) dfs(board, r, c, root, res);
}
}
return res;
}
private void dfs(char[][] b, int r, int c, Node p, List<String> res) {
char ch = b[r][c];
if (ch == '#' || p.c[ch - 'a'] == null) return;
Node cur = p.c[ch - 'a'];
if (cur.word != null) { res.add(cur.word); cur.word = null; }
b[r][c] = '#';
int[] d = {-1, 0, 1, 0, -1};
for (int i = 0; i < 4; i++) {
int nr = r + d[i], nc = c + d[i+1];
if (nr >= 0 && nr < b.length && nc >= 0 && nc < b[0].length) dfs(b, nr, nc, cur, res);
}
b[r][c] = ch;
}
}class Solution {
struct Node { Node* c[26] = {}; string word = ""; };
void dfs(vector<vector<char>>& b, int r, int c, Node* p, vector<string>& res) {
char ch = b[r][c];
if (ch == '#' || !p->c[ch - 'a']) return;
Node* cur = p->c[ch - 'a'];
if (!cur->word.empty()) { res.push_back(cur->word); cur->word = ""; }
b[r][c] = '#';
int d[5] = {-1, 0, 1, 0, -1};
for (int i = 0; i < 4; i++) {
int nr = r + d[i], nc = c + d[i+1];
if (nr >= 0 && nr < b.size() && nc >= 0 && nc < b[0].size()) dfs(b, nr, nc, cur, res);
}
b[r][c] = ch;
}
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
Node* root = new Node();
for (auto& w : words) {
Node* n = root;
for (char ch : w) {
if (!n->c[ch - 'a']) n->c[ch - 'a'] = new Node();
n = n->c[ch - 'a'];
}
n->word = w;
}
vector<string> res;
for (int r = 0; r < board.size(); r++) {
for (int c = 0; c < board[0].size(); c++) {
if (root->c[board[r][c] - 'a']) dfs(board, r, c, root, res);
}
}
return res;
}
};class Solution:
def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
trie = {}
for w in words:
cur = trie
for c in w: cur = cur.setdefault(c, {})
cur['$'] = w
res, m, n = [], len(board), len(board[0])
def dfs(r, c, p):
ch = board[r][c]
node = p[ch]
if '$' in node:
res.append(node['$'])
del node['$']
board[r][c] = '#'
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and board[nr][nc] in node:
dfs(nr, nc, node)
board[r][c] = ch
for r in range(m):
for c in range(n):
if board[r][c] in trie: dfs(r, c, trie)
return resfunction findWords(board, words) {
const root = {};
for (const w of words) {
let n = root;
for (const c of w) { n[c] = n[c] || {}; n = n[c]; }
n.word = w;
}
const res = [], m = board.length, n = board[0].length;
function dfs(r, c, p) {
const ch = board[r][c], cur = p[ch];
if (cur.word) { res.push(cur.word); cur.word = null; }
board[r][c] = '#';
for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && cur[board[nr][nc]]) {
dfs(nr, nc, cur);
}
}
board[r][c] = ch;
}
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (root[board[r][c]]) dfs(r, c, root);
}
}
return res;
} Step 2: Most Optimized
Approach 2: Standalone Word Search Backtracking for Each Word (Baseline)
Time: O(W * M * N * 3^L)
Space: O(L)
For each word in words, runs the classic Word Search grid backtracking function starting from matching first characters. Simple to implement, but redundant when multiple words share prefixes.
Approach 2: Standalone Word Search Backtracking for Each Word (Baseline) Implementation
Approach 2: Standalone Word Search Backtracking for Each Word (Baseline)
class Solution {
public List<String> findWords(char[][] board, String[] words) {
List<String> res = new ArrayList<>();
Set<String> set = new HashSet<>(Arrays.asList(words));
for (String w : set) {
if (exist(board, w)) res.add(w);
}
return res;
}
boolean exist(char[][] board, String word) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == word.charAt(0) && dfs(board, i, j, 0, word)) return true;
}
}
return false;
}
boolean dfs(char[][] b, int r, int c, int idx, String w) {
if (idx == w.length()) return true;
if (r < 0 || r >= b.length || c < 0 || c >= b[0].length || b[r][c] != w.charAt(idx)) return false;
char temp = b[r][c];
b[r][c] = '#';
boolean found = dfs(b, r+1, c, idx+1, w) || dfs(b, r-1, c, idx+1, w) || dfs(b, r, c+1, idx+1, w) || dfs(b, r, c-1, idx+1, w);
b[r][c] = temp;
return found;
}
}class Solution {
bool dfs(vector<vector<char>>& b, int r, int c, int idx, string& w) {
if (idx == w.size()) return true;
if (r < 0 || r >= b.size() || c < 0 || c >= b[0].size() || b[r][c] != w[idx]) return false;
char temp = b[r][c];
b[r][c] = '#';
bool found = dfs(b, r+1, c, idx+1, w) || dfs(b, r-1, c, idx+1, w) || dfs(b, r, c+1, idx+1, w) || dfs(b, r, c-1, idx+1, w);
b[r][c] = temp;
return found;
}
bool exist(vector<vector<char>>& b, string& w) {
for (int i = 0; i < b.size(); i++) {
for (int j = 0; j < b[0].size(); j++) {
if (b[i][j] == w[0] && dfs(b, i, j, 0, w)) return true;
}
}
return false;
}
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
unordered_set<string> unique(words.begin(), words.end());
vector<string> res;
for (auto& w : unique) {
string s = w;
if (exist(board, s)) res.push_back(s);
}
return res;
}
};class Solution:
def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
m, n = len(board), len(board[0])
def exist(word):
def dfs(r, c, idx):
if idx == len(word): return True
if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[idx]: return False
temp = board[r][c]
board[r][c] = '#'
found = dfs(r+1, c, idx+1) or dfs(r-1, c, idx+1) or dfs(r, c+1, idx+1) or dfs(r, c-1, idx+1)
board[r][c] = temp
return found
for i in range(m):
for j in range(n):
if board[i][j] == word[0] and dfs(i, j, 0): return True
return False
return [w for w in set(words) if exist(w)]var findWords = function(board, words) {
const m = board.length, n = board[0].length;
function exist(word) {
function dfs(r, c, idx) {
if (idx === word.length) return true;
if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== word[idx]) return false;
const temp = board[r][c];
board[r][c] = '#';
const found = dfs(r+1, c, idx+1) || dfs(r-1, c, idx+1) || dfs(r, c+1, idx+1) || dfs(r, c-1, idx+1);
board[r][c] = temp;
return found;
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (board[i][j] === word[0] && dfs(i, j, 0)) return true;
}
}
return false;
}
const unique = [...new Set(words)];
return unique.filter(w => exist(w));
};Edge Cases to Watch
- Words sharing common prefixes (e.g. "oath" and "pea")
- Board smaller than target word lengths
- No words found on board (returns empty list [])
- Duplicate words in words input (handled by Trie or Set)
Algorithmic Pattern
View Pattern Guide →
Master the Trie Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Trie pattern.
How to Recognize This Pattern
- "Find all words from a list in a grid"
- Trie prunes search: abort branch if no word shares the prefix
Complexity Analysis
Time Complexity
O(M × N × 4 × 3^(L-1))
Space Complexity
O(∑ word lengths)
Tags
Array String Backtracking Trie Matrix
Frequently Asked Questions
What is the optimal time and space complexity for Word Search II?
The optimal solution for Word Search II achieves O(M × N × 4 × 3^(L-1)) runtime complexity and requires O(∑ word lengths) auxiliary space. Time complexity is O(M * N * 4^(3^(L-1))) bounded by board dimensions and word length L <= 10. Traversal terminates early whenever a prefix does not exist in the Trie. Space complexity is O(sum of word lengths) to store all words in the Trie.
How do I identify that Word Search II requires the Trie pattern?
In technical interviews, look for key problem signals: "Find all words from a list in a grid"; Trie prunes search: abort branch if no word shares the prefix. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Trie strategy.
What critical edge cases must be handled in Word Search II?
Essential edge cases to verify include: Words sharing common prefixes (e.g. "oath" and "pea"); Board smaller than target word lengths; No words found on board (returns empty list []); Duplicate words in words input (handled by Trie or Set). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Word Search II?
Word Search II is a Hard-difficulty question tagged with medium recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Microsoft, Google.