Word Search II
Word Search II is a hard tries problem solved with the trie + backtracking pattern.
The best approach, optimal (trie + backtracking), runs in O(m · n · 3^L + total letters in words) time and O(total letters in words) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (search every word separately) up.
Problem
You are given an m x n grid of lowercase letters board and a list of distinct words words. Return every word from the list that can be traced on the board.
A word is traced by starting at any cell and moving step by step to a cell directly above, below, left or right, reading one letter per cell. The same cell may not be used more than once within one word. You may return the found words in any order.
Examples
Example 1
- Input
board = [["c", "a", "t"], ["o", "r", "s"], ["w", "e", "n"]], words = ["cat", "cart", "crow", "rest", "star", "cow"]- Output
["cat", "cow", "star"]- Why
- cat runs along the top row, cow down the first column and star goes s -> t -> a -> r. cart and crow need letters that are not neighbours, and in rest the e and the s never touch.
Example 2
- Input
board = [["m", "o"], ["o", "n"]], words = ["moon", "mono", "noon"]- Output
["mono"]- Why
- mono goes m -> o -> n -> o around the square. moon would need two o cells next to each other, and noon needs two n cells; neither exists here.
Constraints
m == board.length,n == board[i].length1 <= m, n <= 12board[i][j]is a lowercase English letter.1 <= words.length <= 3 * 10^41 <= words[i].length <= 10words[i]uses lowercase English letters, and all words are distinct.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (search every word separately) | O(W · m · n · 3^L) | O(L) |
| Optimal (trie + backtracking) | O(m · n · 3^L + total letters in words) | O(total letters in words) |
1Brute force (search every word separately)
O(W · m · n · 3^L)For each of W words and each of m · n start cells, the path search can branch three ways at each of up to L letters.O(L)The recursion depth is at most the word length L (apart from the answer).Run the classic single-word board search for each word: try every start cell, and from there walk to neighbouring cells that match the next letter, marking cells on the current path so none is reused. Add the word to the answer if any start succeeds.
- For each word: for each cell, call dfs(cell, index 0).
- dfs(i, j, k): if k equals the word length, return true; if (i, j) is outside the board or board[i][j] != word[k], return false.
- Mark the cell, try the four neighbours with k + 1, then restore the cell.
- Add the word if any call returned true.
class Solution {
public List<String> findWords(char[][] board, String[] words) {
List<String> res = new ArrayList<>();
for (String w : words) {
if (exists(board, w)) res.add(w);
}
return res;
}
private boolean exists(char[][] board, String w) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(board, w, i, j, 0)) return true;
}
}
return false;
}
private boolean dfs(char[][] b, String w, int i, int j, int k) {
if (k == w.length()) return true;
if (i < 0 || j < 0 || i >= b.length || j >= b[0].length || b[i][j] != w.charAt(k)) return false;
char c = b[i][j];
b[i][j] = '#';
boolean found = dfs(b, w, i + 1, j, k + 1) || dfs(b, w, i - 1, j, k + 1)
|| dfs(b, w, i, j + 1, k + 1) || dfs(b, w, i, j - 1, k + 1);
b[i][j] = c;
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(w: str, i: int, j: int, k: int) -> bool:
if k == len(w):
return True
if i < 0 or j < 0 or i >= m or j >= n or board[i][j] != w[k]:
return False
c = board[i][j]
board[i][j] = "#"
found = (dfs(w, i + 1, j, k + 1) or dfs(w, i - 1, j, k + 1)
or dfs(w, i, j + 1, k + 1) or dfs(w, i, j - 1, k + 1))
board[i][j] = c
return found
res = []
for w in words:
if any(dfs(w, i, j, 0) for i in range(m) for j in range(n)):
res.append(w)
return resclass Solution {
bool dfs(vector<vector<char>>& b, const string& w, int i, int j, int k) {
if (k == (int)w.size()) return true;
if (i < 0 || j < 0 || i >= (int)b.size() || j >= (int)b[0].size() || b[i][j] != w[k]) return false;
char c = b[i][j];
b[i][j] = '#';
bool found = dfs(b, w, i + 1, j, k + 1) || dfs(b, w, i - 1, j, k + 1)
|| dfs(b, w, i, j + 1, k + 1) || dfs(b, w, i, j - 1, k + 1);
b[i][j] = c;
return found;
}
bool exists(vector<vector<char>>& b, const string& w) {
for (int i = 0; i < (int)b.size(); i++) {
for (int j = 0; j < (int)b[0].size(); j++) {
if (dfs(b, w, i, j, 0)) return true;
}
}
return false;
}
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> res;
for (const string& w : words) {
if (exists(board, w)) res.push_back(w);
}
return res;
}
};function findWords(board, words) {
const m = board.length, n = board[0].length;
const dfs = (w, i, j, k) => {
if (k === w.length) return true;
if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] !== w[k]) return false;
const c = board[i][j];
board[i][j] = "#";
const found = dfs(w, i + 1, j, k + 1) || dfs(w, i - 1, j, k + 1)
|| dfs(w, i, j + 1, k + 1) || dfs(w, i, j - 1, k + 1);
board[i][j] = c;
return found;
};
const res = [];
for (const w of words) {
let ok = false;
for (let i = 0; i < m && !ok; i++) {
for (let j = 0; j < n && !ok; j++) {
if (dfs(w, i, j, 0)) ok = true;
}
}
if (ok) res.push(w);
}
return res;
}2Optimal (trie + backtracking)
O(m · n · 3^L + total letters in words)Building the trie reads every letter once. Each start cell explores paths of at most L = 10 letters, branching at most three ways after the first step, and only along trie prefixes.O(total letters in words)The trie stores each letter of the words at most once; the recursion is only L deep.Insert all words into a trie and store each complete word at its final node. Start a DFS from every cell and walk the board and the trie together: a step to a neighbouring cell is only taken if the trie has a child for that letter, so the search dies as soon as the path spells something that no word starts with. When the DFS lands on a node holding a word, add it and clear it, so each word is reported once. All words share the work done for their common prefixes.
- Build a trie of all words; at the node where a word ends, store the word.
- For each cell, call dfs(i, j, root).
- dfs: let c = board[i][j]; stop if the cell is marked or node has no child c. Move node to that child.
- If node holds a word, add it to the answer and clear it.
- Mark the cell, recurse into the four neighbours with the child node, then restore the cell.
class Solution {
private static class TrieNode {
TrieNode[] next = new TrieNode[26];
String word;
}
public List<String> findWords(char[][] board, String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode cur = root;
for (char ch : w.toCharArray()) {
int c = ch - 'a';
if (cur.next[c] == null) cur.next[c] = new TrieNode();
cur = cur.next[c];
}
cur.word = w;
}
List<String> res = new ArrayList<>();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
dfs(board, i, j, root, res);
}
}
return res;
}
private void dfs(char[][] b, int i, int j, TrieNode node, List<String> res) {
if (i < 0 || j < 0 || i >= b.length || j >= b[0].length) return;
char ch = b[i][j];
if (ch == '#' || node.next[ch - 'a'] == null) return;
node = node.next[ch - 'a'];
if (node.word != null) {
res.add(node.word);
node.word = null;
}
b[i][j] = '#';
dfs(b, i + 1, j, node, res);
dfs(b, i - 1, j, node, res);
dfs(b, i, j + 1, node, res);
dfs(b, i, j - 1, node, res);
b[i][j] = ch;
}
}class TrieNode:
def __init__(self):
self.next = {}
self.word = None
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = TrieNode()
for w in words:
cur = root
for ch in w:
if ch not in cur.next:
cur.next[ch] = TrieNode()
cur = cur.next[ch]
cur.word = w
m, n = len(board), len(board[0])
res = []
def dfs(i: int, j: int, node: TrieNode) -> None:
if i < 0 or j < 0 or i >= m or j >= n:
return
ch = board[i][j]
if ch not in node.next: # also covers the "#" mark
return
node = node.next[ch]
if node.word is not None:
res.append(node.word)
node.word = None
board[i][j] = "#"
dfs(i + 1, j, node)
dfs(i - 1, j, node)
dfs(i, j + 1, node)
dfs(i, j - 1, node)
board[i][j] = ch
for i in range(m):
for j in range(n):
dfs(i, j, root)
return resclass Solution {
struct TrieNode {
TrieNode* next[26] = {nullptr};
string word;
bool hasWord = false;
};
void dfs(vector<vector<char>>& b, int i, int j, TrieNode* node, vector<string>& res) {
if (i < 0 || j < 0 || i >= (int)b.size() || j >= (int)b[0].size()) return;
char ch = b[i][j];
if (ch == '#' || node->next[ch - 'a'] == nullptr) return;
node = node->next[ch - 'a'];
if (node->hasWord) {
res.push_back(node->word);
node->hasWord = false;
}
b[i][j] = '#';
dfs(b, i + 1, j, node, res);
dfs(b, i - 1, j, node, res);
dfs(b, i, j + 1, node, res);
dfs(b, i, j - 1, node, res);
b[i][j] = ch;
}
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
TrieNode* root = new TrieNode();
for (const string& w : words) {
TrieNode* cur = root;
for (char ch : w) {
int c = ch - 'a';
if (cur->next[c] == nullptr) cur->next[c] = new TrieNode();
cur = cur->next[c];
}
cur->word = w;
cur->hasWord = true;
}
vector<string> res;
for (int i = 0; i < (int)board.size(); i++) {
for (int j = 0; j < (int)board[0].size(); j++) {
dfs(board, i, j, root, res);
}
}
return res;
}
};function findWords(board, words) {
const newNode = () => ({ next: new Map(), word: null });
const root = newNode();
for (const w of words) {
let cur = root;
for (const ch of w) {
if (!cur.next.has(ch)) cur.next.set(ch, newNode());
cur = cur.next.get(ch);
}
cur.word = w;
}
const m = board.length, n = board[0].length;
const res = [];
const dfs = (i, j, node) => {
if (i < 0 || j < 0 || i >= m || j >= n) return;
const ch = board[i][j];
const child = node.next.get(ch); // undefined for the "#" mark too
if (child === undefined) return;
if (child.word !== null) {
res.push(child.word);
child.word = null;
}
board[i][j] = "#";
dfs(i + 1, j, child);
dfs(i - 1, j, child);
dfs(i, j + 1, child);
dfs(i, j - 1, child);
board[i][j] = ch;
};
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) dfs(i, j, root);
}
return res;
}Edge cases to test
- A 1 x 1 board: only one-letter words can match
- A word that can be traced from several start cells must appear only once in the answer
- One word is a prefix of another (like
caandcat): both can be found on the same path - A path may not reuse a cell, even if the letter is needed again
- Boards full of the same letter make naive searches explode
Hints
Hint 1
Searching for each word separately repeats the same board walks again and again for words that share a prefix.
Hint 2
Put all words into a trie. Then one DFS from each cell can follow the trie at the same time, and stops as soon as the letters so far are not a prefix of any word.
Hint 3
Store the full word at its last trie node. When the DFS reaches such a node, record the word and clear it so it is not reported twice. Mark cells as visited by overwriting them temporarily and restore them when backtracking.
FAQ
What is the best time complexity for Word Search II?
Optimal (trie + backtracking) runs in O(m · n · 3^L + total letters in words) time and O(total letters in words) extra space. Building the trie reads every letter once. Each start cell explores paths of at most L = 10 letters, branching at most three ways after the first step, and only along trie prefixes.
Which pattern does Word Search II use?
It is a tries problem that uses the trie + backtracking pattern.
Is there a brute force solution for Word Search II?
Yes. Brute force (search every word separately) takes O(W · m · n · 3^L) time and O(L) space. Run the classic single-word board search for each word: try every start cell, and from there walk to neighbouring cells that match the next letter, marking cells on the current path so none is reused.
Which edge cases should I test for Word Search II?
A 1 x 1 board: only one-letter words can match; A word that can be traced from several start cells must appear only once in the answer; One word is a prefix of another (like ca and cat): both can be found on the same path; A path may not reuse a cell, even if the letter is needed again; Boards full of the same letter make naive searches explode.