Skip to content

Practice Word Search II

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Hard#212
LeetCode Problem

Word Search II

Problem Statement

Given an m x n board of characters and a list of strings words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Source: Word Search II on LeetCode. Use the original task for its coding environment and submissions.

Examples

# 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

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] is a lowercase English letter.
1 <= words.length <= 3 * 10^4
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
All the strings of words are unique.

How to solve Word Search II

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

Load every word into a trie and run one backtracking search from each cell that walks the trie and the board together, so each path explored is a prefix of some remaining word rather than a search repeated per word.

Why brute force is not enough

Running single-word backtracking for each of up to 3 * 10^4 words costs roughly m * n * 4^L per word with L up to 10, about 10^12 steps in total, and re-explores prefixes shared by many words.

Approach

  1. Insert every word into a trie, storing the complete word at its terminal node so a match is reported without rebuilding the string.
  2. From each cell whose letter is a child of the root, run depth-first search carrying the current trie node; the invariant is that the cells on the current path spell that node's prefix.
  3. On entering a cell, mark it used by temporarily overwriting the letter, record the word if the node is terminal and clear that marker so it is reported once, then recurse into neighbors whose letters are children of the node.
  4. Restore the cell when backtracking, and unlink any child node that has become empty so dead prefixes are never revisited.

Walkthrough of Example 1

board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"] → ["eat","oath"]

  1. The trie root has children o, p, e, and r.
  2. From o at row 0 column 0, the a at row 0 column 1 gives oa, the t at row 1 column 1 gives oat, and the h at row 2 column 1 completes oath, which is recorded.
  3. No cell holds p, so pea never starts, and the e at row 1 column 0 has neighbors o, t, and i, none of them a, so that start dies.
  4. The e at row 1 column 3 has neighbor a at row 1 column 2, which has neighbor t at row 1 column 1, completing eat.
  5. The r at row 2 column 3 has neighbors e, k, and v, none of which is a, so rain fails. The result {eat, oath} matches the expected [eat, oath].

Time and space

Time O(m * n * 4 * 3^(L-1)) · Space O(total characters in words). m and n are the board dimensions and L the longest word; each start branches into 4 then at most 3 directions per step, though pruning makes real runs far smaller, and the trie holds at most one node per character.

Interview pitfalls

  • Reporting a word twice when it occurs at several positions; clear the terminal marker or use a set.
  • Forgetting to restore the cell after backtracking, which blocks later paths and misses words.
  • Reusing a cell within one word; example 2 needs b twice for abcb and must return an empty list.

Follow-up questions interviewers ask

  • How would you adapt the search if diagonal moves were allowed?
  • If the board is fixed but word lists arrive in many queries, what would you precompute?

Further reading on the technique: Trie

Related LeetCode Problems

Practice more problems similar to Word Search II.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.