#212 Word Search II
frequently reported atUberAirbnbByteDance / TikTokAmazonMicrosoftGoogle
the problem
In plain words
Given an m×n board of letters and a list of words, return every word that can be formed by a path of horizontally or vertically adjacent cells, using each cell at most once per word.
in board = ["oaan","etae","ihkr","iflv"], words = ["oath","pea","eat","rain"]
out ["eat","oath"]
Any order is accepted.
in board = ["ab","cd"], words = ["abcb"]
out []
The second 'b' would reuse a cell.
- 1 ≤ m, n ≤ 12
- 1 ≤ words.length ≤ 3·10⁴
- 1 ≤ words[i].length ≤ 10
- Words are unique, lowercase
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTrie (prefix tree)Backtracking on a grid
Don't search the board once per word. Put all words into a trie and run one DFS per start cell that walks the board and the trie together — the moment the trie has no child for the next letter, that whole branch is dead for every word.
solutions
From brute force to optimal
For each word, try every start cell with backtracking DFS (LC 79).
- For each word: for each cell, DFS matching word[i], marking cells on the path.
- Add the word if any start succeeds.
Per word and start cell, the DFS has 4 first moves then at most 3 (no going back) for L−1 more letters.
Recursion depth; the board itself is reused by marking.
class Solution { public List<String> findWords(char[][] board, String[] words) { List<String> found = new ArrayList<>(); for (String word : new LinkedHashSet<>(Arrays.asList(words))) { if (exists(board, word)) found.add(word); // one full board search per word } return found; } 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, 0, r, c)) return true; return false; } private boolean dfs(char[][] board, String word, int i, int r, int c) { if (i == word.length()) return true; if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false; if (board[r][c] != word.charAt(i)) return false; char saved = board[r][c]; board[r][c] = '#'; // mark: don't reuse this cell boolean ok = dfs(board, word, i + 1, r + 1, c) || dfs(board, word, i + 1, r - 1, c) || dfs(board, word, i + 1, r, c + 1) || dfs(board, word, i + 1, r, c - 1); board[r][c] = saved; // unmark on the way back return ok; }}Build a trie of all words (store the word at its end node). DFS from every cell, stepping into the trie child for the cell's letter; stop when it's missing.
- Insert all words; on the last node set
node.word = w. - dfs(r, c, parent): skip out-of-bounds and used cells ('#').
- node = parent.children[letter]; if null → prune.
- If node.word != null → add it and set it to null (no duplicates).
- Mark the cell, recurse in 4 directions, unmark.
- If node is now a leaf with no word, remove it from parent — later searches skip it.
S to build the trie; each start cell explores at most the 4·3^(L−1) paths — but only along prefixes some word has, which is far fewer in practice.
One node per letter of all words; the DFS is at most L = 10 deep.
class Solution { private static class Node { Node[] children = new Node[26]; String word; // the full word that ends here (null if none) } public List<String> findWords(char[][] board, String[] words) { Node root = new Node(); for (String w : words) { Node cur = root; for (char ch : w.toCharArray()) { int i = ch - 'a'; if (cur.children[i] == null) cur.children[i] = new Node(); cur = cur.children[i]; } cur.word = w; } List<String> found = new ArrayList<>(); for (int r = 0; r < board.length; r++) for (int c = 0; c < board[0].length; c++) dfs(board, r, c, root, found); return found; } private void dfs(char[][] board, int r, int c, Node parent, List<String> found) { if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return; char ch = board[r][c]; if (ch == '#') return; Node node = parent.children[ch - 'a']; if (node == null) return; if (node.word != null) { found.add(node.word); node.word = null; // report each word only once } board[r][c] = '#'; dfs(board, r + 1, c, node, found); dfs(board, r - 1, c, node, found); dfs(board, r, c + 1, node, found); dfs(board, r, c - 1, node, found); board[r][c] = ch; if (node.word == null && isLeaf(node)) parent.children[ch - 'a'] = null; } private boolean isLeaf(Node node) { for (Node child : node.children) if (child != null) return false; return true; }}Dry run
in the room
How to say it in the interview
talk track
- Start with "run Word Search I per word" and its cost — then point out the repeated work.
- Explain the trie as a set of all prefixes that are still worth exploring.
- Mention the two optimisations: storing the word on the node (no StringBuilder) and trimming finished leaves.
- Complexity: be honest that the worst case is still exponential in L; the trie makes it practical.
traps
- Not restoring the cell after DFS — later starts see a corrupted board.
- Adding a word every time it's found → duplicates in the answer.
- Checking
board[r][c]before the bounds check → ArrayIndexOutOfBoundsException.
what they ask next
Follow-ups
What if the board were huge and the word list tiny?
Then the brute force per word (with early exits) can be fine; the trie pays off when W is large.
Words in a text instead of a grid?
That's multi-pattern string matching: a trie with failure links (Aho–Corasick) scans the text once in O(text + matches + S).
before you submit
Edge cases to test
- A word that needs the same cell twice ("aba" on ["ab"]) → not found.
- One word is a prefix of another ("a", "aa") → both can be found on one path.
- The same word reachable from many cells → report it once.
practise next
Similar problems
- #79Word SearchMediumin Backtracking
- #211Design Add and Search Words Data StructureMediumin Tries
- #208Implement Trie (Prefix Tree)Mediumin Tries