63.Word Search II

HardBlind 75Tries · 3/3

Problem

Given an m x n grid of letters board and a list of strings words, return all words from the list that can be formed on the board.

A word is formed from a path of horizontally or vertically adjacent cells, and the same cell may not be used more than once within a single word. Each found word appears once in the output, in any order.

Examples

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"]
Explanation: "oath" goes o(0,0) a(0,1) t(1,1) h(2,1); "eat" goes e(1,3) a(1,2) t(1,1).

Input:  board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []
Explanation: Reaching the second 'b' would require reusing cell (0,1).

Constraints

m == board.length, n == board[i].length
1 <= m, n <= 12
1 <= words.length <= 3 * 10^4
1 <= words[i].length <= 10
board[i][j] and words[i] consist of lowercase English letters; all words[i] are unique.

💡 Key Insight

Running a separate DFS per word repeats the same grid exploration thousands of times. Instead, put all words in a trie and run one DFS per starting cell that walks the board and the trie together: a path is abandoned the moment its letters are not a prefix of any word. Storing the full word at its terminal node, clearing it once found, and pruning emptied trie branches keeps the search from revisiting exhausted prefixes.

Brute Force (Word Search per Word)

SpaceO(L) recursion depth.

Intuition

Solve "Word Search I" for each word independently: try every cell as a start and backtrack along matching letters. Stop at the first successful placement of a word.

Algorithm

For each word in words:
For every cell (r, c), run dfs(r, c, 0); if it succeeds, add word and move to the next word.
dfs(r, c, i): if i == word.length() return true; return false if out of bounds or board[r][c] != word[i].
Mark the cell '#', recurse into 4 neighbours with i + 1, then restore the letter.

Visualization

word = "eat"
start (1,3)='e' -> (1,2)='a' -> (1,1)='t' -> i == 3 -> found

word = "rain"
start (2,3)='r' -> neighbours: e, k, v (no 'a') -> fail; no other 'r' -> not found

Code

java

import java.util.ArrayList;
import java.util.List;

class 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);
            }
        }
        return result;
    }

    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, r, c, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int r, int c, int i) {
        if (i == word.length()) {
            return true;
        }
        if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] != word.charAt(i)) {
            return false;
        }
        char saved = board[r][c];
        board[r][c] = '#'; // mark visited for this path
        boolean found = dfs(board, word, r + 1, c, i + 1) || dfs(board, word, r - 1, c, i + 1)
                || dfs(board, word, r, c + 1, i + 1) || dfs(board, word, r, c - 1, i + 1);
        board[r][c] = saved; // backtrack
        return found;
    }
}

Complexity

Time: O(W · m · n · 4 · 3^(L-1)) — for each of W words, each cell may start a DFS that branches up to 3 ways for L steps. Too slow for W = 3 · 10^4.
Space: O(L) recursion depth.

Trie + Backtracking

SpaceO(total chars) for the trie, O(L) recursion.

Intuition

Build a trie from all words and store each word at its terminal node. Start a DFS from every cell, carrying the current trie node. Moving to a neighbour is only allowed if the trie has a child for that letter, so every path explored is a prefix of at least one word — all words are searched simultaneously.

Algorithm

Insert every word; at the last node set node.word = word.
For each cell, call dfs(r, c, root).
In dfs: let ch = board[r][c]; return if ch == '#' or node.children[ch] is null.
Move to next; if next.word != null, add it to the result and set next.word = null (avoid duplicates).
Mark the cell, recurse into the 4 neighbours with next, restore the cell.

Visualization

Trie for ["oath","pea","eat","rain"] — DFS from (0,0)='o' follows o → a → t → h on the board and in the trie at the same time:

flowchart TD
    R["root"] -->|"o"| O["o"]
    R -->|"p"| P["p"]
    R -->|"e"| E["e"]
    R -->|"r"| RR["r"]
    O -->|"a"| OA["oa"]
    OA -->|"t"| OAT["oat"]
    OAT -->|"h"| OATH["oath<br/>word = 'oath'"]
    P -->|"e"| PE["pe"]
    PE -->|"a"| PEA["pea<br/>word = 'pea'"]
    E -->|"a"| EA["ea"]
    EA -->|"t"| EAT["eat<br/>word = 'eat'"]
    RR -->|"a"| RA["ra"]

The board has no 'p', so the whole pea branch is never entered.

Code

java

import java.util.ArrayList;
import java.util.List;

class Solution {
    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word; // non-null when a word ends here
    }

    private final List<String> result = new ArrayList<>();

    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode node = root;
            for (char ch : w.toCharArray()) {
                int i = ch - 'a';
                if (node.children[i] == null) {
                    node.children[i] = new TrieNode();
                }
                node = node.children[i];
            }
            node.word = w;
        }
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                dfs(board, r, c, root);
            }
        }
        return result;
    }

    private void dfs(char[][] board, int r, int c, TrieNode node) {
        if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) {
            return;
        }
        char ch = board[r][c];
        if (ch == '#' || node.children[ch - 'a'] == null) {
            return; // visited, or no word continues with this letter
        }
        TrieNode next = node.children[ch - 'a'];
        if (next.word != null) {
            result.add(next.word);
            next.word = null; // report each word once
        }
        board[r][c] = '#';
        dfs(board, r + 1, c, next);
        dfs(board, r - 1, c, next);
        dfs(board, r, c + 1, next);
        dfs(board, r, c - 1, next);
        board[r][c] = ch;
    }
}

Complexity

Time: O(m · n · 4 · 3^(L-1)) — one trie-guided DFS per cell, depth at most L = 10; plus O(total chars) to build the trie.
Space: O(total chars) for the trie, O(L) recursion.

Trie + Backtracking with PruningOptimal

SpaceO(total chars) for the trie, O(L) recursion.

Intuition

Approach 2 still re-walks prefixes whose words were all found already. Once a node has no word and no children left, it is useless — remove it from its parent. Later DFS calls then fail at the parent immediately. Tracking a childCount per node makes the "is this node empty?" check O(1).

Algorithm

Build the trie as before, incrementing childCount when a child is created.
DFS identical to Approach 2, but after recursing into next:
- If next.word == null && next.childCount == 0, set node.children[ch] = null and decrement node.childCount.
Optionally stop early when result.size() == words.length.

Dry Run

flowchart LR
    A["DFS finds 'eat'<br/>at node eat"] --> B["eat.word = null<br/>eat has 0 children"]
    B --> C["remove eat from ea<br/>ea.childCount = 0"]
    C --> D["remove ea from e<br/>e.childCount = 0"]
    D --> E["remove e from root"]
    E --> F["later cells with 'e'<br/>return immediately"]

Code

java

import java.util.ArrayList;
import java.util.List;

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

    private final List<String> result = new ArrayList<>();

    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode node = root;
            for (char ch : w.toCharArray()) {
                int i = ch - 'a';
                if (node.children[i] == null) {
                    node.children[i] = new TrieNode();
                    node.childCount++;
                }
                node = node.children[i];
            }
            node.word = w;
        }
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                dfs(board, r, c, root);
                if (result.size() == words.length) {
                    return result; // every word found
                }
            }
        }
        return result;
    }

    private void dfs(char[][] board, int r, int c, TrieNode node) {
        if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) {
            return;
        }
        char ch = board[r][c];
        if (ch == '#') {
            return;
        }
        int idx = ch - 'a';
        TrieNode next = node.children[idx];
        if (next == null) {
            return;
        }
        if (next.word != null) {
            result.add(next.word);
            next.word = null;
        }
        board[r][c] = '#';
        dfs(board, r + 1, c, next);
        dfs(board, r - 1, c, next);
        dfs(board, r, c + 1, next);
        dfs(board, r, c - 1, next);
        board[r][c] = ch;
        // prune: this branch can no longer produce any word
        if (next.word == null && next.childCount == 0) {
            node.children[idx] = null;
            node.childCount--;
        }
    }
}

Complexity

Time: O(m · n · 4 · 3^(L-1)) worst case, but pruning shrinks the trie as words are found, so real runs are much faster.
Space: O(total chars) for the trie, O(L) recursion.

Complexity Comparison

Approach	Time	Space
Word Search per Word	O(W · m · n · 3^L)	O(L)
Trie + Backtracking	O(m · n · 3^L)	O(total chars)
Trie + Pruning	O(m · n · 3^L), far fewer visits in practice	O(total chars)

Common Pitfalls

Adding the same word twice when it can be formed from several starting cells — clear node.word after recording it (or use a set).
Returning after finding a word: a found word may be a prefix of another ("oa" and "oath"), so keep exploring.
Forgetting to restore board[r][c] after the recursive calls, which corrupts later searches.
Checking node.children[ch - 'a'] before checking for the '#' marker gives a negative index.