Loading…

hardTriesLC #212Frequently asked

Word Search II

Q: How do you solve Word Search II using the Word Search I Per Word (Naive Baseline — too slow) approach?

When to use it: State it first to anchor the complexity, then explain why W independent searches are wasteful and pivot to the trie. The most direct idea: we already know how to find a single word on the board (Word Search I), so loop over the word list and run that search for each one. **Why it's the natural first attempt.** It reuses a known sub-routine and is obviously correct — find word 1, find word 2, and so on. In an interview it's worth stating to show you can decompose the problem. **Why it's hopelessly slow.** Each call scans the whole board and DFS-branches up to 4^L. Repeating that for W = 3×10⁴ words is O(W · m · n · 4^L). Worse, the redundancy is structural: if `"oath"`, `"oat"`, and `"oar"` are all in the list, each search re-walks the `o→a` prefix on the board independently. The board work for shared prefixes is duplicated W-fold. **Why the trie fixes exactly this.** A trie merges all the words by prefix, so the grid is walked once and the shared `o→a` is explored a single time. The board DFS is driven by 'what letters can still continue some word', which is precisely the trie's children set. That's the optimisation: collapse W searches into one prefix-guided traversal. Time complexity: O(W · m · n · 4^L). Space complexity: O(L) recursion.

LCPractice

Tries · 3 of 4 · 11 min

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.

In plain English

Find which of the given dictionary words can be spelled by a connected, non-repeating path of horizontally/vertically adjacent cells. With up to 3×10⁴ words, searching for each independently is too slow — the trick is to drive a single grid traversal with a trie so all words are checked in one sweep, sharing the work of common prefixes.

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"]
Note: "oath" snakes o(0,0)→a(0,1)→t(1,1)→h(2,1); "eat" is e(1,0)→a(1,1)... adjacency holds. "pea" and "rain" cannot be spelled by adjacent cells.

Example 2

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []
Note: "abcb" would reuse the 'b' cell, which is forbidden, so it isn't found.

Example 3

Input: board = [["a"]], words = ["a"]
Output: ["a"]
Note: Single cell matches the single-letter word; its trie terminal node holds "a".

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⁴
1 ≤ words[i].length ≤ 10
All strings in words are unique

Clarifying questions4First question: Can the same board cell be reused within one word?Explore questions

Q1.Can the same board cell be reused within one word?
No — within a single word's path, each cell is used at most once. That's why we mark a cell visited before recursing and restore it after.
Q2.Are diagonal moves allowed?
No, only the 4 orthogonal neighbours (up/down/left/right).
Q3.Can a word appear multiple times on the board — do we report it twice?
No, the output is the SET of words found. We dedupe by clearing the trie's terminal marker the first time we collect a word.
Q4.Could there be many words sharing a prefix?
Yes, and that's exactly what makes the trie pay off — the shared prefix is walked once in the grid DFS instead of once per word.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Don't run Word Search I once per word. Build a trie of ALL the words, then DFS the grid a single time, advancing through the trie as you step between cells. A cell only continues a branch if its letter is a child in the trie — the trie prunes dead paths instantly. When you reach a node with a word stored, collect it.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you spot that running Word Search I per word is wastefully redundant, and can fuse the whole word list into one trie so a single grid DFS is pruned by what's still reachable. It's about combining two patterns (grid DFS + trie) under a complexity constraint.

Where candidates slip

Calling the single-word search W times (O(W · m · n · 4^L)), or forgetting to restore the visited mark on backtrack, or returning duplicates because terminal markers aren't cleared.

How to stand out

Store the word at the terminal node (no path rebuild), dedupe by nulling the marker on collection, and prune empty trie leaves so the DFS shrinks as words are found — plus reason about why the trie's shared prefixes kill the redundant work.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Word Search I Per Word (Naive Baseline — too slow)	`O(W · m · n · 4^L)`	`O(L) recursion`	State it first to anchor the complexity, then explain why W independent searches are wasteful and pivot to the trie.	Read
2	Trie + Single Grid DFS with Pruning (Optimal)Optimal	`O(W·L) to build trie + O(m·n·4·3^(L-1)) to search`	`O(W·L) trie + O(L) recursion`	The intended solution. Frame it as 'put the words in a trie, then DFS the board once, letting the trie tell us which letters still continue a word'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Trie of the word list drives one grid DFS

How to read it:Words ["oath","oat","eat"] share the o→a→t prefix, stored once. The green path is what the grid DFS follows; a board letter with no matching child is pruned instantly. Double-circle nodes carry a stored word.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Word Search I Per Word (Naive Baseline — too slow)

TimeO(W · m · n · 4^L)SpaceO(L) recursion

State it first to anchor the complexity, then explain why W independent searches are wasteful and pivot to the trie.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You already know how to find ONE word on a board (Word Search I): DFS from each cell, matching letters.

2Hint 2Explore hint

The obvious extension is to call that search once for each word in the list.

3Hint 3Explore hint

Now count the cost: W separate full-board DFS runs, each up to O(m·n·4^L). The shared prefixes between words are re-explored every time — that's the waste.

A · Core idea

The most direct idea: we already know how to find a single word on the board (Word Search I), so loop over the word list and run that search for each one.

Why it's the natural first attempt. It reuses a known sub-routine and is obviously correct — find word 1, find word 2, and so on. In an interview it's worth stating to show you can decompose the problem.

Why it's hopelessly slow. Each call scans the whole board and DFS-branches up to 4^L. Repeating that for W = 3×10⁴ words is O(W · m · n · 4^L). Worse, the redundancy is structural: if "oath", "oat", and "oar" are all in the list, each search re-walks the o→a prefix on the board independently. The board work for shared prefixes is duplicated W-fold.

Why the trie fixes exactly this. A trie merges all the words by prefix, so the grid is walked once and the shared o→a is explored a single time. The board DFS is driven by 'what letters can still continue some word', which is precisely the trie's children set. That's the optimisation: collapse W searches into one prefix-guided traversal.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

words = ["oat","oath","oar"] on a board

search "oat"

DFS whole board, walk o→a→t

Stateexplores o→a once

Final resultCorrect results, but O(W · m · n · 4^L) — the prefix o→a walked W times

C · Code with teaching comments

Reference implementation previewclass Solution { public List<String> findWords(char[][] board, String[] words) { List<String> result = new ArrayList<>(); for (String word : words) { if (exists(board, word)) result.add(word);Explore the full code

solution.javaJava

Word Search I Per Word (Naive Baseline — too slow) — reference

3 teaching notes

1
class Solution {
2
    public List<String> findWords(char[][] board, String[] words) {
3
        List<String> result = new ArrayList<>();
4
        // One independent full-board search per word — the source of the W factor.
5
        for (String word : words) {
6
            if (exists(board, word)) result.add(word);
7
        }
8
        return result;
9
    }
10
 
11
    private boolean exists(char[][] board, String word) {
12
        int m = board.length, n = board[0].length;
13
        for (int r = 0; r < m; r++) {
14
            for (int c = 0; c < n; c++) {
15
                // Tries starting the word at every cell; shared prefixes get re-walked
16
                // across words.
17
                if (dfs(board, r, c, word, 0)) return true;
18
            }
19
        }
20
        return false;
21
    }
22
 
23
    private boolean dfs(char[][] board, int r, int c, String word, int idx) {
24
        if (idx == word.length()) return true;
25
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length
26
                || board[r][c] != word.charAt(idx)) return false;
27
        char tmp = board[r][c];
28
        // Mark visited so the path can't reuse a cell; restored after recursing.
29
        board[r][c] = '#';
30
        boolean found = dfs(board, r + 1, c, word, idx + 1)
31
                || dfs(board, r - 1, c, word, idx + 1)
32
                || dfs(board, r, c + 1, word, idx + 1)
33
                || dfs(board, r, c - 1, word, idx + 1);
34
        board[r][c] = tmp;
35
        return found;
36
    }
37
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.37 lines

D · Why it works and complexityO(W · m · n · 4^L) timeO(L) recursion spaceOpen the invariant and proofExplore the proof

The naive cost is dominated by re-exploring shared prefixes once per word. Anytime you find yourself running the same prefix-walk repeatedly across many patterns, a trie is the structure that lets you do that shared work exactly once.

ComplexityO(W · m · n · 4^L) time, O(L) recursion space — For each of W words we run a full Word Search I: every one of m·n cells can start a DFS that branches into ~4 directions up to L deep → O(m·n·4^L) per word, times W words. With W up to 3×10⁴ this is far too slow.

E · Edge cases and pitfalls4Many words sharing the prefix "oa" — Each word re-explores the o→a board path from scratch; correctness holds but the redundancy is exactly what the trie eliminates.Explore edge cases

Edge cases handled

Many words sharing the prefix "oa"Each word re-explores the o→a board path from scratch; correctness holds but the redundancy is exactly what the trie eliminates.

Pitfalls

Assuming reusing Word Search I is fine — the W multiplier on an exponential DFS is the trap.
Forgetting to restore board[r][c] after the DFS, corrupting the grid for the next word's search.
Not early-exiting on the first successful start cell, doing even more redundant work.

03.2

Approach 2 of 2 · Optimal

Trie + Single Grid DFS with Pruning (Optimal)

TimeO(W·L) to build trie + O(m·n·4·3^(L-1)) to searchSpaceO(W·L) trie + O(L) recursion

The intended solution. Frame it as 'put the words in a trie, then DFS the board once, letting the trie tell us which letters still continue a word'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of searching per word, what if a single grid DFS knew which letters could still extend SOME word? A trie of all the words answers that.

2Hint 2Explore hint

Build a trie of every word, storing the full word string at each terminal node. Then DFS from each cell, advancing a trie pointer alongside the grid position.

3Hint 3Explore hint

At a cell, if its letter isn't a child of the current trie node, stop — that branch can't spell any word. When you land on a node holding a word, collect it and null the marker to dedupe. Optionally prune empty leaves.

A · Core idea

Two patterns fused: a trie of the dictionary and a single backtracking DFS over the grid, with the trie acting as a pruning oracle.

Why store the words in a trie first. The naive solution wastes time re-walking shared prefixes once per word. A trie merges all words by prefix, so "oath", "oat", "oar" share one o→a path. Now the grid DFS can ask a single, cheap question at each step — 'is this board letter a child of my current trie node?' — and that question simultaneously checks all words that could continue here. We store the full word string on the terminal node so that when we arrive, we can collect it without reconstructing the path.

Why the trie is a pruning oracle. In the naive DFS we'd branch in all 4 directions and only discover failure after matching L characters. Here, the instant a neighbouring cell's letter isn't in node.children, we stop — no word starts with that prefix, so the whole subtree is dead. This collapses the exponential 4^L blow-up: we only descend where the trie says a word is still possible. That single if ch not in node.children: return is the heart of the speed-up.

Why we dedupe by nulling the terminal marker. A board may spell the same word via different paths, and we want each word once. When we collect a word at a terminal node, we clear its stored string (node.word = null). The word is now in the result, and future arrivals at that node won't re-add it — simpler and safer than a separate result-set membership check.

Why backtracking still applies on the grid. A word's path can't reuse a cell, so before recursing into neighbours we mark the current cell visited (overwrite with a sentinel like '#'), and we restore it afterwards. Skipping the restore would corrupt the board for every other start cell. Optional leaf pruning: once a trie node has no children left (all its words found and removed), we can detach it from its parent so subsequent DFS stops even earlier — the trie literally shrinks as words are discovered.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

words = ["oath","eat"], starting DFS near the 'o' and 'e' cells

Interactive diagram

The pruning decision at each cell

start (0,0)='o'

Active call / nodeSupporting contextReturned stateNot active

Each grid step asks the trie one question. A miss kills the branch (the optimisation); a terminal node collects a word and clears its marker.

Final result["oath", "eat"]

C · Code with teaching comments

solution.javaJava

Trie + Single Grid DFS with Pruning (Optimal) — optimal

6 teaching notes

1
class Solution {
2
    private static class TrieNode {
3
        TrieNode[] children = new TrieNode[26];
4
        // Store the full word at its terminal node — collect it directly without
5
        // rebuilding the path.
6
        String word = null;
7
    }
8
 
9
    private TrieNode buildTrie(String[] words) {
10
        TrieNode root = new TrieNode();
11
        for (String w : words) {
12
            TrieNode node = root;
13
            for (char c : w.toCharArray()) {
14
                int i = c - 'a';
15
                if (node.children[i] == null) node.children[i] = new TrieNode();
16
                node = node.children[i];
17
            }
18
            // After inserting, stamp the complete word on the last node.
19
            node.word = w;
20
        }
21
        return root;
22
    }
23
 
24
    public List<String> findWords(char[][] board, String[] words) {
25
        TrieNode root = buildTrie(words);
26
        List<String> result = new ArrayList<>();
27
        for (int r = 0; r < board.length; r++) {
28
            for (int c = 0; c < board[0].length; c++) {
29
                dfs(board, r, c, root, result);
30
            }
31
        }
32
        return result;
33
    }
34
 
35
    private void dfs(char[][] board, int r, int c, TrieNode node, List<String> result) {
36
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return;
37
        char ch = board[r][c];
38
        // The pruning line: bail if the cell is visited OR no word continues with this
39
        // letter.
40
        if (ch == '#' || node.children[ch - 'a'] == null) return;
41
        TrieNode next = node.children[ch - 'a'];
42
        if (next.word != null) {
43
            result.add(next.word);
44
            // Dedupe — clear the marker so the same word isn't collected twice via
45
            // another path.
46
            next.word = null;
47
        }
48
        // Mark visited before exploring neighbours (no cell reuse within a word).
49
        board[r][c] = '#';
50
        dfs(board, r + 1, c, next, result);
51
        dfs(board, r - 1, c, next, result);
52
        dfs(board, r, c + 1, next, result);
53
        dfs(board, r, c - 1, next, result);
54
        // Restore the cell on backtrack so other paths/start cells see the original
55
        // board.
56
        board[r][c] = ch;
57
    }
58
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.58 lines

D · Why it works and complexityO(W·L) to build trie + O(m·n·4·3^(L-1)) to search timeO(W·L) trie + O(L) recursion spaceOpen the invariant and proofExplore the proof

The mental flip is from 'for each word, search the grid' to 'search the grid once; let the trie decide which words are still alive'. The trie turns multi-pattern search into single-pass pruning: shared prefixes are explored once, impossible branches die immediately, and found words are removed so the search space only shrinks. This grid-DFS-pruned-by-a-trie is the canonical hard-trie pattern.

ComplexityO(W·L) to build trie + O(m·n·4·3^(L-1)) to search time, O(W·L) trie + O(L) recursion space — Building the trie costs O(W·L) over all words. The grid DFS visits each of m·n start cells; from there the path length is bounded by the longest word L, with the first step having 4 directions and each subsequent step ~3 (can't revisit the immediate previous cell) → O(m·n·4·3^(L-1)). Crucially the trie prunes any branch whose letters don't continue a word, so in practice the explored tree is tiny compared to the naive 4^L. Space is the trie O(W·L) plus O(L) recursion depth.

E · Edge cases and pitfalls5Two board paths spell the same word — First arrival collects it and nulls next.word; the second arrival sees word == null and adds nothing → no duplicates.Explore edge cases

Edge cases handled

Two board paths spell the same wordFirst arrival collects it and nulls next.word; the second arrival sees word == null and adds nothing → no duplicates.
A word that is a prefix of another, e.g. "oat" and "oath"Landing on the 'oat' node collects "oat" but the DFS continues to 'h' for "oath" — both are found because collection doesn't stop the descent.

Pitfalls

Not restoring board[r][c] after recursion — corrupts the grid so later start cells misbehave.
Forgetting to null the terminal word — the same word appears multiple times in the output.
Rebuilding the matched string by concatenation during DFS instead of storing it on the terminal node — extra work and bug surface.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewclass Solution { private static class TrieNode { TrieNode[] children = new TrieNode[26]; String word = null; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

class Solution {
    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word = null;
    }

private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode node = root;
            for (char c : w.toCharArray()) {
                int i = c - 'a';
                if (node.children[i] == null) node.children[i] = new TrieNode();
                node = node.children[i];
            }
            node.word = w;
        }
        return root;
    }

public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = buildTrie(words);
        List<String> result = new ArrayList<>();
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                dfs(board, r, c, root, result);
            }
        }
        return result;
    }

private void dfs(char[][] board, int r, int c, TrieNode node, List<String> result) {
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return;
        char ch = board[r][c];
        if (ch == '#' || node.children[ch - 'a'] == null) return;
        TrieNode next = node.children[ch - 'a'];
        if (next.word != null) {
            result.add(next.word);
            next.word = null;
        }
        board[r][c] = '#';
        dfs(board, r + 1, c, next, result);
        dfs(board, r - 1, c, next, result);
        dfs(board, r, c + 1, next, result);
        dfs(board, r, c - 1, next, result);
        board[r][c] = ch;
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forgetting to restore the visited cell

Marking board[r][c] = '#' blocks cell reuse within a path, but if you don't restore it on the way back, the cell stays blocked for every other path and start cell — words that legitimately need it are missed.

Explore the code comparison

Don't write this

board[r][c] = '#';
dfs(board, r + 1, c, next, result);
dfs(board, r - 1, c, next, result);
// missing restore — board permanently mutated

Write this instead

board[r][c] = '#';
dfs(board, r + 1, c, next, result);
dfs(board, r - 1, c, next, result);
// ... other directions ...
board[r][c] = ch; // restore on backtrack

Duplicate words in the output

If the same word can be traced via two paths and you never clear its marker, it gets collected twice. Nulling next.word on first collection both dedupes and prunes future work.

Explore the code comparison

Don't write this

if nxt.word is not None:
    result.append(nxt.word)
    # marker left set — same word can be added again

Write this instead

if nxt.word is not None:
    result.append(nxt.word)
    nxt.word = None  # collected once, then cleared

Stopping the DFS after collecting a word

When a node holds a word that is also a prefix of a longer word ("oat" inside "oath"), returning right after collecting would miss the longer word. Collect, then keep descending.

Explore the code comparison

Don't write this

if nxt.word is not None:
    result.append(nxt.word)
    return  # WRONG — "oath" never reached after "oat"

Write this instead

if nxt.word is not None:
    result.append(nxt.word)
    nxt.word = None
# fall through and continue DFS into neighbours

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Trie of the word list + single grid DFS, pruned by the trie

Code pattern to memorize

build trie of words (store word at terminal node)
for each cell (r,c):
    dfs(r, c, trie.root)

dfs(r, c, node):
    ch = board[r][c]
    if ch not in node.children: return   # PRUNE
    nxt = node.children[ch]
    if nxt.word: collect(nxt.word); nxt.word = None  # dedupe
    mark visited; explore 4 neighbours; unmark
    if nxt has no children: prune leaf

Rules to remember

1Build one trie of all words; DFS the grid once — never re-scan per word.
2Store the full word string at the terminal node so you collect without rebuilding the path.
3After collecting a word, null out its terminal marker to avoid duplicate results.
4Mark the current cell visited before recursing, restore it after (classic backtracking).
5Prune trie leaves: once a node has no children left, detach it so future DFS stops earlier.

Use this pattern when

Search a grid/board for MANY target words at once
Multiple-pattern matching where patterns share prefixes
A single-word DFS exists but is called once per word (too slow)
Any 'find all dictionary words inside a structure' task

Choose another pattern when

Only ONE word to find → plain Word Search I DFS, no trie needed
Words share no prefixes and are few → the trie overhead may not pay off
You can match on a 1D string → Aho-Corasick / KMP may fit better
Grid is enormous but word list tiny → per-word search might actually win

Interview takeaway

The trie flips the loop: instead of 'for each word, search the grid', it's 'walk the grid once, let the trie tell you which words are still possible'. Shared prefixes are explored once, dead branches die immediately, and pruning collected words/empty leaves keeps the DFS lean. It's the showcase of trie-as-a-pruning-oracle.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical Trie-as-pruning-oracle over a grid DFS. Recognise it when you must find MANY words in a structure: merge the words into a trie, traverse once, and let missing children prune dead branches. Same family as Word Search I (single word) and Add-and-Search-Words (trie + DFS).

Practice queueDirect variations and pattern siblings

Direct follow-ups

Word Search
Coming soon
The single-word baseline — one DFS, no trie. Word Search II generalises it to many words.
Implement Trie (Prefix Tree)
Build this trie first; storing the word on the terminal node is the small tweak here.
Design Add and Search Words Data Structure
Also trie + DFS, but the branching comes from '.' wildcards rather than grid neighbours.
Word Squares
Coming soon
Trie of prefixes again — backtrack row by row, using the trie to find words with a required prefix.

Same pattern

←

Design Add and Search Words Data Structure

Continue · Next problem

Replace Words

hardTriesLC #212Frequently asked

Word Search II

LCPractice

Tries · 3 of 4 · 11 min

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

In plain English

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"]
Note: "oath" snakes o(0,0)→a(0,1)→t(1,1)→h(2,1); "eat" is e(1,0)→a(1,1)... adjacency holds. "pea" and "rain" cannot be spelled by adjacent cells.

Example 2

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []
Note: "abcb" would reuse the 'b' cell, which is forbidden, so it isn't found.

Example 3

Input: board = [["a"]], words = ["a"]
Output: ["a"]
Note: Single cell matches the single-letter word; its trie terminal node holds "a".

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⁴
1 ≤ words[i].length ≤ 10
All strings in words are unique

Clarifying questions4First question: Can the same board cell be reused within one word?Explore questions

Q1.Can the same board cell be reused within one word?
No — within a single word's path, each cell is used at most once. That's why we mark a cell visited before recursing and restore it after.
Q2.Are diagonal moves allowed?
No, only the 4 orthogonal neighbours (up/down/left/right).
Q3.Can a word appear multiple times on the board — do we report it twice?
No, the output is the SET of words found. We dedupe by clearing the trie's terminal marker the first time we collect a word.
Q4.Could there be many words sharing a prefix?
Yes, and that's exactly what makes the trie pay off — the shared prefix is walked once in the grid DFS instead of once per word.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Calling the single-word search W times (O(W · m · n · 4^L)), or forgetting to restore the visited mark on backtrack, or returning duplicates because terminal markers aren't cleared.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Word Search I Per Word (Naive Baseline — too slow)	`O(W · m · n · 4^L)`	`O(L) recursion`	State it first to anchor the complexity, then explain why W independent searches are wasteful and pivot to the trie.	Read
2	Trie + Single Grid DFS with Pruning (Optimal)Optimal	`O(W·L) to build trie + O(m·n·4·3^(L-1)) to search`	`O(W·L) trie + O(L) recursion`	The intended solution. Frame it as 'put the words in a trie, then DFS the board once, letting the trie tell us which letters still continue a word'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Trie of the word list drives one grid DFS

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Word Search I Per Word (Naive Baseline — too slow)

TimeO(W · m · n · 4^L)SpaceO(L) recursion

State it first to anchor the complexity, then explain why W independent searches are wasteful and pivot to the trie.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You already know how to find ONE word on a board (Word Search I): DFS from each cell, matching letters.

2Hint 2Explore hint

The obvious extension is to call that search once for each word in the list.

3Hint 3Explore hint

Now count the cost: W separate full-board DFS runs, each up to O(m·n·4^L). The shared prefixes between words are re-explored every time — that's the waste.

A · Core idea

The most direct idea: we already know how to find a single word on the board (Word Search I), so loop over the word list and run that search for each one.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

words = ["oat","oath","oar"] on a board

search "oat"

DFS whole board, walk o→a→t

Stateexplores o→a once

Final resultCorrect results, but O(W · m · n · 4^L) — the prefix o→a walked W times

C · Code with teaching comments

solution.javaJava

Word Search I Per Word (Naive Baseline — too slow) — reference

3 teaching notes

1
class Solution {
2
    public List<String> findWords(char[][] board, String[] words) {
3
        List<String> result = new ArrayList<>();
4
        // One independent full-board search per word — the source of the W factor.
5
        for (String word : words) {
6
            if (exists(board, word)) result.add(word);
7
        }
8
        return result;
9
    }
10
 
11
    private boolean exists(char[][] board, String word) {
12
        int m = board.length, n = board[0].length;
13
        for (int r = 0; r < m; r++) {
14
            for (int c = 0; c < n; c++) {
15
                // Tries starting the word at every cell; shared prefixes get re-walked
16
                // across words.
17
                if (dfs(board, r, c, word, 0)) return true;
18
            }
19
        }
20
        return false;
21
    }
22
 
23
    private boolean dfs(char[][] board, int r, int c, String word, int idx) {
24
        if (idx == word.length()) return true;
25
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length
26
                || board[r][c] != word.charAt(idx)) return false;
27
        char tmp = board[r][c];
28
        // Mark visited so the path can't reuse a cell; restored after recursing.
29
        board[r][c] = '#';
30
        boolean found = dfs(board, r + 1, c, word, idx + 1)
31
                || dfs(board, r - 1, c, word, idx + 1)
32
                || dfs(board, r, c + 1, word, idx + 1)
33
                || dfs(board, r, c - 1, word, idx + 1);
34
        board[r][c] = tmp;
35
        return found;
36
    }
37
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.37 lines

D · Why it works and complexityO(W · m · n · 4^L) timeO(L) recursion spaceOpen the invariant and proofExplore the proof

Edge cases handled

Many words sharing the prefix "oa"Each word re-explores the o→a board path from scratch; correctness holds but the redundancy is exactly what the trie eliminates.

Pitfalls

Assuming reusing Word Search I is fine — the W multiplier on an exponential DFS is the trap.
Forgetting to restore board[r][c] after the DFS, corrupting the grid for the next word's search.
Not early-exiting on the first successful start cell, doing even more redundant work.

03.2

Approach 2 of 2 · Optimal

Trie + Single Grid DFS with Pruning (Optimal)

TimeO(W·L) to build trie + O(m·n·4·3^(L-1)) to searchSpaceO(W·L) trie + O(L) recursion

The intended solution. Frame it as 'put the words in a trie, then DFS the board once, letting the trie tell us which letters still continue a word'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of searching per word, what if a single grid DFS knew which letters could still extend SOME word? A trie of all the words answers that.

2Hint 2Explore hint

Build a trie of every word, storing the full word string at each terminal node. Then DFS from each cell, advancing a trie pointer alongside the grid position.

3Hint 3Explore hint

A · Core idea

Two patterns fused: a trie of the dictionary and a single backtracking DFS over the grid, with the trie acting as a pruning oracle.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

words = ["oath","eat"], starting DFS near the 'o' and 'e' cells

Interactive diagram

The pruning decision at each cell

start (0,0)='o'

Active call / nodeSupporting contextReturned stateNot active

Each grid step asks the trie one question. A miss kills the branch (the optimisation); a terminal node collects a word and clears its marker.

Final result["oath", "eat"]

C · Code with teaching comments

solution.javaJava

Trie + Single Grid DFS with Pruning (Optimal) — optimal

6 teaching notes

1
class Solution {
2
    private static class TrieNode {
3
        TrieNode[] children = new TrieNode[26];
4
        // Store the full word at its terminal node — collect it directly without
5
        // rebuilding the path.
6
        String word = null;
7
    }
8
 
9
    private TrieNode buildTrie(String[] words) {
10
        TrieNode root = new TrieNode();
11
        for (String w : words) {
12
            TrieNode node = root;
13
            for (char c : w.toCharArray()) {
14
                int i = c - 'a';
15
                if (node.children[i] == null) node.children[i] = new TrieNode();
16
                node = node.children[i];
17
            }
18
            // After inserting, stamp the complete word on the last node.
19
            node.word = w;
20
        }
21
        return root;
22
    }
23
 
24
    public List<String> findWords(char[][] board, String[] words) {
25
        TrieNode root = buildTrie(words);
26
        List<String> result = new ArrayList<>();
27
        for (int r = 0; r < board.length; r++) {
28
            for (int c = 0; c < board[0].length; c++) {
29
                dfs(board, r, c, root, result);
30
            }
31
        }
32
        return result;
33
    }
34
 
35
    private void dfs(char[][] board, int r, int c, TrieNode node, List<String> result) {
36
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return;
37
        char ch = board[r][c];
38
        // The pruning line: bail if the cell is visited OR no word continues with this
39
        // letter.
40
        if (ch == '#' || node.children[ch - 'a'] == null) return;
41
        TrieNode next = node.children[ch - 'a'];
42
        if (next.word != null) {
43
            result.add(next.word);
44
            // Dedupe — clear the marker so the same word isn't collected twice via
45
            // another path.
46
            next.word = null;
47
        }
48
        // Mark visited before exploring neighbours (no cell reuse within a word).
49
        board[r][c] = '#';
50
        dfs(board, r + 1, c, next, result);
51
        dfs(board, r - 1, c, next, result);
52
        dfs(board, r, c + 1, next, result);
53
        dfs(board, r, c - 1, next, result);
54
        // Restore the cell on backtrack so other paths/start cells see the original
55
        // board.
56
        board[r][c] = ch;
57
    }
58
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.58 lines

D · Why it works and complexityO(W·L) to build trie + O(m·n·4·3^(L-1)) to search timeO(W·L) trie + O(L) recursion spaceOpen the invariant and proofExplore the proof

Edge cases handled

Two board paths spell the same wordFirst arrival collects it and nulls next.word; the second arrival sees word == null and adds nothing → no duplicates.
A word that is a prefix of another, e.g. "oat" and "oath"Landing on the 'oat' node collects "oat" but the DFS continues to 'h' for "oath" — both are found because collection doesn't stop the descent.

Pitfalls

Not restoring board[r][c] after recursion — corrupts the grid so later start cells misbehave.
Forgetting to null the terminal word — the same word appears multiple times in the output.
Rebuilding the matched string by concatenation during DFS instead of storing it on the terminal node — extra work and bug surface.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewclass Solution { private static class TrieNode { TrieNode[] children = new TrieNode[26]; String word = null; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

class Solution {
    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word = null;
    }

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forgetting to restore the visited cell

Explore the code comparison

Don't write this

board[r][c] = '#';
dfs(board, r + 1, c, next, result);
dfs(board, r - 1, c, next, result);
// missing restore — board permanently mutated

Write this instead

board[r][c] = '#';
dfs(board, r + 1, c, next, result);
dfs(board, r - 1, c, next, result);
// ... other directions ...
board[r][c] = ch; // restore on backtrack

Duplicate words in the output

If the same word can be traced via two paths and you never clear its marker, it gets collected twice. Nulling next.word on first collection both dedupes and prunes future work.

Explore the code comparison

Don't write this

if nxt.word is not None:
    result.append(nxt.word)
    # marker left set — same word can be added again

Write this instead

if nxt.word is not None:
    result.append(nxt.word)
    nxt.word = None  # collected once, then cleared

Stopping the DFS after collecting a word

When a node holds a word that is also a prefix of a longer word ("oat" inside "oath"), returning right after collecting would miss the longer word. Collect, then keep descending.

Explore the code comparison

Don't write this

if nxt.word is not None:
    result.append(nxt.word)
    return  # WRONG — "oath" never reached after "oat"

Write this instead

if nxt.word is not None:
    result.append(nxt.word)
    nxt.word = None
# fall through and continue DFS into neighbours

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Trie of the word list + single grid DFS, pruned by the trie

Code pattern to memorize

build trie of words (store word at terminal node)
for each cell (r,c):
    dfs(r, c, trie.root)

dfs(r, c, node):
    ch = board[r][c]
    if ch not in node.children: return   # PRUNE
    nxt = node.children[ch]
    if nxt.word: collect(nxt.word); nxt.word = None  # dedupe
    mark visited; explore 4 neighbours; unmark
    if nxt has no children: prune leaf

Rules to remember

1Build one trie of all words; DFS the grid once — never re-scan per word.
2Store the full word string at the terminal node so you collect without rebuilding the path.
3After collecting a word, null out its terminal marker to avoid duplicate results.
4Mark the current cell visited before recursing, restore it after (classic backtracking).
5Prune trie leaves: once a node has no children left, detach it so future DFS stops earlier.

Use this pattern when

Search a grid/board for MANY target words at once
Multiple-pattern matching where patterns share prefixes
A single-word DFS exists but is called once per word (too slow)
Any 'find all dictionary words inside a structure' task

Choose another pattern when

Only ONE word to find → plain Word Search I DFS, no trie needed
Words share no prefixes and are few → the trie overhead may not pay off
You can match on a 1D string → Aho-Corasick / KMP may fit better
Grid is enormous but word list tiny → per-word search might actually win

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Word Search
Coming soon
The single-word baseline — one DFS, no trie. Word Search II generalises it to many words.
Implement Trie (Prefix Tree)
Build this trie first; storing the word on the terminal node is the small tweak here.
Design Add and Search Words Data Structure
Also trie + DFS, but the branching comes from '.' wildcards rather than grid neighbours.
Word Squares
Coming soon
Trie of prefixes again — backtrack row by row, using the trie to find words with a required prefix.

Same pattern

←

Design Add and Search Words Data Structure

Continue · Next problem

Replace Words