Difficulty: HardTries

Word Search II

Problem in Plain English

Given a board of letters and a long list of candidate words, return every word that can be spelled by stepping through horizontally or vertically adjacent cells. No cell may be reused within a single word.

Problem Statement

Given an m x n board of characters and a list of strings words, return all words that appear on the board.

Each word must be built from sequentially adjacent cells, where adjacent means sharing a side horizontally or vertically. The same cell may not be used twice within one word, and each listed word is reported at most once.

Constraints

m == board.length
n == board[i].length
Board dimensions satisfy $1 \leq m,n \leq 12$ .
board[i][j] is a lowercase English letter.
The candidate count is between 1 and $3 \times 10^4$ .
Every word length is between 1 and 10.
words[i] consists of lowercase English letters.
All strings in words are unique.

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"]

The board spells oath down the path (0,0) to (0,1) to (1,1) to (2,1), and spells eat nearby, while pea and rain cannot be completed.

Example 2

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

No path spells abcb. From the top-left a, the only b is top-right; its unused neighbor is d, not c. The bottom-left c is diagonal to b, which is forbidden. Reusing any earlier cell is also forbidden.

Example 3

Input: board = [["a","a"]], words = ["a","aa","aaa"]
Output: ["a","aa"]

Either cell spells a, but that word is returned only once. Both cells together spell aa. aaa would reuse a cell, so it fails. Finding the shorter word must not stop the search for the longer one sharing its prefix; output order is arbitrary.

Intuition

A grid path must follow matching letters without revisiting a cell. Searching separately for oath, pea, eat and rain repeats this work, while a trie stores all candidate prefixes so one path can test several words together. In Example 1, o → a → t → h reaches the terminal for oath; an unrecognized prefix can stop immediately. A temporary visited marker belongs only to the current path and must be restored before another path begins.

Approaches

DFS per Word

Solution Details

Reveal DFS per Word: intuition, complexity, and code

Intuition

Finding one word on a board is a standard depth-first search, so the simplest plan repeats that search independently for every candidate word. The board gets rescanned from scratch each time, which turns painful once the word list grows into the thousands.

Step-by-Step Logic

For each candidate, scan every possible starting cell and recursively match the next character along four side-adjacent neighbors. Mark matched cells during the path and always restore them afterward.
For Example 1, oath begins at (0,0). Down to (1,0)=e fails for a, up is outside, and right to (0,1)=a works. Down to (1,1)=t, then (2,1)=h, matches the remaining letters.
When all four letters match, return success and restore h, t, a, then o while unwinding; append oath only once.
Repeat independently for pea: no starting cell holds p. For eat, the first e at (1,0) has no adjacent a, but (1,3) → (1,2) → (1,1) spells eat.
For rain, the r at (2,3) has neighbors v, e, outside and k, none of which is the required a. Return the words found, oath and eat, in any order.

Why It Works

At dfs(r,c,word,i), earlier marked cells spell exactly the first i letters and are unavailable for this path. A call accepts a cell only if it is in bounds and matches the next letter. Marking that cell before recursion prevents reuse; exploring all four directions covers every side-adjacent continuation. Reaching i equal to the word length proves a valid spelling, while exhausting all starts proves absence. Restoring the cell even when a recursive branch succeeds makes later starts and later words see the original board. Each unique candidate is appended at most once because its search stops at the first success.

Dry Run

DFS per Word: variable states at each step
Candidate / next index	Cell or attempt	Matched path / visited change	Outcome
oath, i=0	(0,0)=o	empty → o; mark (0,0)	seek a
oath, i=1	(1,0)=e; (-1,0) outside	o unchanged	reject both
oath, i=1	(0,1)=a	o → oa; mark (0,1)	seek t
oath, i=2	(1,1)=t	oa → oat; mark (1,1)	seek h
oath, i=3	(2,1)=h	oat → oath; mark (2,1)	all letters matched
oath, i=4	base case before any next-cell check	oath is complete	true
oath unwind	h → t → a → o frames	restore all four letters	append oath; stop this word
pea, i=0	every start	no p anywhere; no marks	absent
eat, i=0	(1,0)=e	mark e; neighbors i,o,t,outside reject a; restore e	try later start
eat, i=0	(1,3)=e	mark e; down r, up n, right outside reject a	left remains
eat, i=1	(1,2)=a	e → ea; mark a; k,a,e reject t	try left
eat, i=2	(1,1)=t	ea → eat; mark t; next i=3 succeeds	restore t,a,e; append eat
rain, i=0	(2,3)=r	mark r; v,e,outside,k reject a; restore r	no other r; absent
return	original board restored	result [oath, eat]	same output set as [eat, oath]

Complexity Analysis

Time Complexity

O(WB3^D)

Space Complexity

O(D+K)

W is the candidate count, B is rows times columns, L is the longest candidate, D=min(L,B), and K is the returned word count. Each start has at most four first moves and at most three later moves because its predecessor is marked; O(3^D) bounds the explored paths, with an additional constant-depth failed call when L exceeds B. The stack uses O(D+1) frames including a possible final failed/base-case call, board marking allocates no visited matrix, and output retains O(K) references to immutable input strings. No sorting or path-string copies are performed. This deliberately simple baseline repeats prefix work per word and can be too slow on large dictionaries.

Code

Solution.java

1import java.util.ArrayList;2import java.util.List;3
4class Solution {5    private char[][] board;6    private int rows;7    private int cols;8
9    public List<String> findWords(char[][] board, String[] words) {10        this.board = board;11        this.rows = board.length;12        this.cols = board[0].length;13        List<String> res = new ArrayList<>();14        for (String word : words) {15            if (exists(word)) {16                res.add(word);17            }18        }19        return res;20    }21
22    private boolean exists(String word) {23        for (int r = 0; r < rows; r++) {24            for (int c = 0; c < cols; c++) {25                if (dfs(r, c, word, 0)) {26                    return true;27                }28            }29        }30        return false;31    }32
33    private boolean dfs(int r, int c, String word, int i) {34        // All letters already matched; no extra neighbor is required.35        if (i == word.length()) {36            return true;37        }38        if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] != word.charAt(i)) {39            return false;40        }41        char saved = board[r][c];42        // This marker belongs only to the current path, preventing cell reuse.43        board[r][c] = '#';44        boolean found = dfs(r + 1, c, word, i + 1) || dfs(r - 1, c, word, i + 1)45                || dfs(r, c + 1, word, i + 1) || dfs(r, c - 1, word, i + 1);46        // Restore even after a successful short-circuit branch.47        board[r][c] = saved;48        return found;49    }50}

Hints

Hint 1

Searching the board once per word repeats the same walks thousands of times, so look for a way to test all words together.

Hint 2

A trie of the candidates tells you instantly whether the current path is still a prefix of anything worth finishing.

Hint 3

When a word is found, erase it from its terminal node so later paths cannot report it a second time.

Edge Cases

A word longer than the total cell count, which is impossible without reusing cells.
Candidates sharing long prefixes, such as app and apple, which the trie explores together.
A word reachable by several routes, which must still appear only once in the answer.
A one-cell board can match only a one-letter word, and many routes spelling the same word still produce one result.
Calling the same solver again must build a fresh trie and fresh result; previously returned lists remain unchanged.

Common Mistakes and Interview Tips

Forgetting to restore the cell letter after exploring its neighbors, which blocks every later path through that cell.
Reporting a found word every time its path is walked instead of clearing it from the trie node.
Carrying the built-up string through the search and testing prefixes by scanning, which loses the whole point of the trie.
Returning immediately on a trie terminal and missing longer words that share its prefix.
Clearing or reordering the input dictionary to deduplicate results; clear only the private trie terminal payload.
Keeping a Java result list as an accumulating field across calls; replace it with a fresh list for each invocation.

Key Takeaway

When one grid must be tested against a whole dictionary, plant the dictionary in a trie and let one backtracking walk prune every dead prefix at once.