Word Search II (LC 212)

Pattern: Trie + Backtracking DFS on Grid
Difficulty: Hard
Key Concept: Put all words in one trie; DFS from each cell, following trie edges; on end, record word and prune node to avoid duplicates.

Problem Statement

Given an m x n board of characters and a list of strings words, return all words from words that can be built from sequentially adjacent cells (up/down/left/right), without reusing the same cell in one word.

Input: char[][] board, String[] words
Output: List<String> — all words found (order may vary unless sorted).

---

1. Algorithm & Pseudocode

Brute force

1. For each word, run Word Search I style DFS from every cell — O(N × m × n × 4^L) roughly, N = number of words, L max length; huge overlap rescanning board.

Pseudocode

found = []
for w in words:
    if existsOnBoard(board, w):
        found.add(w)
return found

Optimal

1. Build trie of all words.
2. DFS from each cell (r,c):
   • Match board[r][c] to trie child; move.
   • Mark cell visited (e.g., temp set to '#' or boolean grid).
   • If node end, add word to answer; optionally remove end or prune path to speed up.
   • Backtrack unmark.
3. Pruning: remove trie leaf after word found to cut future work (optional optimization).

Pseudocode

trie = build(words)
ans = set

function dfs(r, c, node):
    if out of bounds or cell visited or no child for letter: return
    ch = board[r][c]
    nxt = node.child[ch]
    mark visited
    if nxt.end: ans.add(nxt.word)
    for each neighbor: dfs(nr, nc, nxt)
    unmark

for each cell: dfs(i, j, root)
return ans

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Single trie shares prefixes among words — one DFS path on board can match many words simultaneously.
• Why not brute per word: The board is scanned repeatedly; trie amortizes character checks.
• Visited marking prevents cycles; backtracking restores state for other paths.
• Pruning the trie after collecting a word prevents duplicate outputs and shrinks branching.

---

3. The Dry Run

Board

o a a n
e t a e
i h k r
i f l v

Words: oath, pea, eat, rain (classic example).

Trie fragment (simplified)

root
├─ o → a → t → h*
├─ p → e → a*
├─ e → a → t*
└─ r → a → i → n*

Starting at (0,0) 'o': walk o-a-t-h along valid neighbors → find oath.

ASCII (first letters on board)

(0,0)o   a   a   n
       ...

Trace conceptually: DFS follows trie edges only if the next letter exists on an unvisited neighbor.

---

4. Java Solution

Brute Force

import java.util.*;

class SolutionBrute {
    private int m, n;
    private char[][] b;

    // Time: O(W * m * n * 4^L) roughly, W = words.length
    public List<String> findWords(char[][] board, String[] words) {
        b = board;
        m = board.length;
        n = board[0].length;
        List<String> ans = new ArrayList<>();
        for (String w : words) {
            if (exists(w)) ans.add(w);
        }
        return ans;
    }

    private boolean exists(String w) {
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (dfs(i, j, 0, w, new boolean[m][n])) return true;
        return false;
    }

    private boolean dfs(int r, int c, int k, String w, boolean[][] vis) {
        if (k == w.length()) return true;
        if (r < 0 || c < 0 || r >= m || c >= n || vis[r][c]) return false;
        if (b[r][c] != w.charAt(k)) return false;
        vis[r][c] = true;
        int[][] d = {{1,0},{-1,0},{0,1},{0,-1}};
        for (int[] t : d) {
            if (dfs(r + t[0], c + t[1], k + 1, w, vis)) return true;
        }
        vis[r][c] = false;
        return false;
    }
}

Optimal

import java.util.*;

class Solution {
    private static class Node {
        Node[] next = new Node[26];
        String word; // store full word at terminal for easy collect
    }

    private char[][] board;
    private int m, n;
    private final List<String> ans = new ArrayList<>();

    // Time: O(m*n*4^L + S) with pruning much better; S = sum of word lengths for trie build
    // Space: O(S) trie + O(L) recursion
    public List<String> findWords(char[][] board, String[] words) {
        this.board = board;
        m = board.length;
        n = board[0].length;
        Node root = buildTrie(words);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(i, j, root);
            }
        }
        return ans;
    }

    private Node buildTrie(String[] words) {
        Node root = new Node();
        for (String w : words) {
            Node cur = root;
            for (int i = 0; i < w.length(); i++) {
                int idx = w.charAt(i) - 'a';
                if (cur.next[idx] == null) cur.next[idx] = new Node();
                cur = cur.next[idx];
            }
            cur.word = w;
        }
        return root;
    }

    private void dfs(int r, int c, Node node) {
        if (r < 0 || c < 0 || r >= m || c >= n) return;
        char ch = board[r][c];
        if (ch == '#' || node.next[ch - 'a'] == null) return;
        Node nxt = node.next[ch - 'a'];
        if (nxt.word != null) {
            ans.add(nxt.word);
            nxt.word = null; // avoid duplicates
        }
        board[r][c] = '#';
        dfs(r + 1, c, nxt);
        dfs(r - 1, c, nxt);
        dfs(r, c + 1, nxt);
        dfs(r, c - 1, nxt);
        board[r][c] = ch;
        // optional: prune empty nxt children for speed (advanced)
    }
}

---

5. The “Java vs. Others” Edge

• Mutating board[r][c] = '#' saves a boolean[][] (space); remember to restore.
• Store String word at terminal instead of boolean end to avoid StringBuilder reconstruction.
• ArrayList for answer; use HashSet if duplicates possible before dedupe (problem usually distinct words).
• Large inputs: pruning trie nodes after they become useless reduces branching (implement carefully).

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute per word	O(W·m·n·4^L)	O(m·n) vis per search	Re-scans board
Trie + DFS	O(m·n·4^L + S) worst	O(S) trie + O(L) stack	Shared prefixes; pruning helps a lot

L = max word length, S = total characters in all words.