166. Word Search II

🔗 LeetCode Problem: 212. Word Search II
📊 Difficulty: Hard
🏷️ Topics: Trie, Array, String, Backtracking, Matrix

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.

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

---

🌳 Visual Understanding - The Complete Picture

The Problem We're Solving:

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

Words to find: ["oath", "pea", "eat", "rain"]

Question: Which words exist as paths on the board?

Path rules:
  1. Move only horizontally or vertically (4 directions)
  2. Can't reuse same cell in one word
  3. Must form exact word from dictionary

Check "oath":
  Start at 'o' (0,0)
  → 'a' (0,1) [right]
  → 't' (1,1) [down]
  → 'h' (2,1) [down]
  Found! ✓

Check "eat":
  Start at 'e' (1,3)
  → 'a' (1,2) [left]
  → 't' (1,1) [left]
  Found! ✓

Check "pea":
  No 'p' on board ✗

Check "rain":
  Have 'r' but can't form "rain" ✗

Result: ["eat", "oath"]

KEY INSIGHT: Need to search from EVERY cell for EVERY word! 😰

The Brute Force Nightmare:

APPROACH 1: Naive Backtracking
For each word in dictionary:
  For each cell on board:
    Try DFS backtracking to form word

Problem:
  - w words in dictionary
  - m*n cells on board
  - Each DFS: O(4^L) where L = word length

  Time: O(w * m * n * 4^L) - ASTRONOMICAL! 😱

Example: 30000 words, 12x12 board, avg word length 8
  = 30000 * 144 * 4^8 = 30000 * 144 * 65536
  = 282,864,640,000 operations!

This is IMPOSSIBLY slow! 🐌

The Trie Revolution:

APPROACH 2: Trie + Backtracking
1. Build Trie with ALL words (done once)
2. For each cell on board:
   - Start DFS
   - Navigate Trie as we explore board
   - If Trie says "no such prefix" → STOP early!
   - If we reach word end → found a word!

Benefits:
  - Trie acts as a FILTER
  - Prunes impossible paths EARLY
  - Multiple words found in ONE traversal
  - Shares common prefixes

Time: O(m * n * 4^L) - Much better!
Why? We only traverse board m*n times, not w*m*n times!

Example: Same input
  = 144 * 4^8 = 144 * 65536 = 9,437,184 operations

30,000x faster! 🚀

Visual: How Trie Guides Search:

Words: ["oath", "pea", "eat", "rain"]

Build Trie:
                    root
                  /  |  \
                 o   p   e   r
                 |   |   |   |
                 a   e   a   a
                 |   |   |   |
                 t   a   t   i
                 |           |
                [h]          n
              (oath)      (rain)

Now search board starting from (0,0) = 'o':

Start at 'o' (0,0):
  Check Trie: root has child 'o'? YES! ✓
  Continue DFS from this cell

Move to 'a' (0,1):
  Check Trie: 'o' node has child 'a'? YES! ✓
  Continue DFS

Move to 't' (1,1):
  Check Trie: 'oa' node has child 't'? YES! ✓
  Continue DFS

Move to 'h' (2,1):
  Check Trie: 'oat' node has child 'h'? YES! ✓
  AND it's isEndOfWord? YES! Found "oath"! ✓

Contrast with starting at (0,0) = 'o' but going down:
Move to 'e' (1,0):
  Check Trie: 'o' node has child 'e'? NO! ✗
  STOP! Don't waste time exploring this path!

This is the POWER of Trie:
  - Guides the search
  - Prunes bad paths early
  - No wasted exploration! 🎯

---

🧠 The AHA Moment - Trie + Backtracking Synergy

Understanding the Two Components:

COMPONENT 1: Trie (Word Dictionary)
Purpose: Pre-process all words into prefix tree
Benefit: O(1) check if prefix exists

COMPONENT 2: Backtracking (Board Exploration)
Purpose: Explore all possible paths on board
Benefit: Systematic exhaustive search with pruning

SYNERGY: Trie-Guided Backtracking
- Backtracking explores board
- Trie validates each step
- If Trie says "no such prefix" → backtrack immediately
- If Trie says "this is a word" → record it!

Without Trie: Explore everything blindly
With Trie: Explore intelligently with early stopping! 🎯

The Backtracking Template:

Standard DFS Backtracking:

void dfs(cell, path):
    if (out of bounds) return
    if (already visited) return
    if (found solution) record it

    mark cell as visited

    // Try all 4 directions
    dfs(up, path)
    dfs(down, path)
    dfs(left, path)
    dfs(right, path)

    unmark cell (backtrack)

With Trie Enhancement:

void dfs(cell, trieNode):
    if (out of bounds) return
    if (already visited) return

    char = board[cell]

    // KEY: Check Trie first!
    if (trieNode has no child for char) return  // Prune!

    nextNode = trieNode.children[char]

    if (nextNode.isEndOfWord):
        record word  // Found a word!

    mark cell as visited

    // Try all 4 directions with SAME nextNode
    dfs(up, nextNode)
    dfs(down, nextNode)
    dfs(left, nextNode)
    dfs(right, nextNode)

    unmark cell (backtrack)

The difference: Trie node travels WITH the DFS! 🔑

Visual: DFS with Trie Navigation:

Board:
  o  a  a  n
  e  t  a  e

Trie for "oath":
  root → o → a → t → h (word)

DFS from (0,0):

Step 1: At (0,0) = 'o', node = root
  root has child 'o'? YES
  Move to Trie node 'o'
  Mark (0,0) as visited
  Try 4 directions:

Step 2: Try right (0,1) = 'a', node = 'o'
  'o' node has child 'a'? YES
  Move to Trie node 'a'
  Mark (0,1) as visited
  Try 4 directions:

Step 3: Try down (1,1) = 't', node = 'a'
  'a' node has child 't'? YES
  Move to Trie node 't'
  Mark (1,1) as visited
  Try 4 directions:

Step 4: Try down (2,1) = 'h', node = 't'
  't' node has child 'h'? YES
  Move to Trie node 'h'
  Is 'h' node a word end? YES! ✓
  Found "oath"!

  Continue exploring to find more words...

Backtrack:
  Unmark (2,1)
  Unmark (1,1)
  Unmark (0,1)
  Unmark (0,0)

The Trie node and board position move TOGETHER! 🎯

Pruning in Action:

Board:
  o  a  a  n
  e  t  a  e

Trie has no word starting with "oe"

DFS from (0,0) = 'o':

Try going down to (1,0) = 'e':
  Current node = 'o' (in Trie)
  Check: 'o' node has child 'e'?
  NO! ✗

  STOP immediately!
  Don't explore (2,0), (1,1), (0,0) again from here
  Don't waste time on impossible paths!

This saves MASSIVE amounts of computation:
  Without Trie: Would explore all 4^k paths
  With Trie: Stops at first invalid character

The pruning is EXPONENTIAL in benefit! 🚀

---

🎯 Solution Approaches

Approach 1: Brute Force (For Comparison)

Idea: For each word, try DFS from every cell.

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();

        for (String word : words) {
            if (existsOnBoard(board, word)) {
                result.add(word);
            }
        }

        return result;
    }

    private boolean existsOnBoard(char[][] board, String word) {
        int m = board.length, n = board[0].length;

        // Try starting from each cell
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, 0, i, j, new boolean[m][n])) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int index, 
                        int i, int j, boolean[][] visited) {
        if (index == word.length()) return true;
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
        if (visited[i][j] || board[i][j] != word.charAt(index)) return false;

        visited[i][j] = true;
        boolean found = dfs(board, word, index + 1, i - 1, j, visited) ||
                        dfs(board, word, index + 1, i + 1, j, visited) ||
                        dfs(board, word, index + 1, i, j - 1, visited) ||
                        dfs(board, word, index + 1, i, j + 1, visited);
        visited[i][j] = false;

        return found;
    }
}

Analysis: - Time Complexity: O(w * m * n * 4^L) where w = words, mn = board size, L = word length - Space Complexity: O(L) for recursion + O(mn) for visited array - Pros: Simple to understand - Cons: EXTREMELY slow, many words cause Time Limit Exceeded

---

Approach 2: Trie + Backtracking (Optimal Solution) ⭐

Idea: Build Trie once, then DFS from each cell guided by Trie.

class Solution {
    private class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word = null;  // Store complete word at end
    }

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

    public List<String> findWords(char[][] board, String[] words) {
        // Step 1: Build Trie with all words
        for (String word : words) {
            insert(word);
        }

        // Step 2: DFS from each cell on board
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, i, j, root);
            }
        }

        return result;
    }

    private void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.word = word;
    }

    private void dfs(char[][] board, int i, int j, TrieNode node) {
        // Boundary check
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return;
        }

        char ch = board[i][j];

        // Already visited (marked as '#')
        if (ch == '#') return;

        // Check if current character exists in Trie
        int index = ch - 'a';
        if (node.children[index] == null) {
            return;  // No word with this prefix, prune!
        }

        node = node.children[index];

        // Found a word!
        if (node.word != null) {
            result.add(node.word);
            node.word = null;  // Avoid duplicates
        }

        // Mark as visited
        board[i][j] = '#';

        // Explore all 4 directions
        dfs(board, i - 1, j, node);  // Up
        dfs(board, i + 1, j, node);  // Down
        dfs(board, i, j - 1, node);  // Left
        dfs(board, i, j + 1, node);  // Right

        // Backtrack: restore original character
        board[i][j] = ch;
    }
}

Optimizations Applied:

// OPTIMIZATION 1: Store word at end node
node.word = word;  // During insert
// Benefit: No need to build word during DFS

// OPTIMIZATION 2: Set word to null after found
if (node.word != null) {
    result.add(node.word);
    node.word = null;  // Avoid adding same word twice
}

// OPTIMIZATION 3: Modify board instead of visited array
board[i][j] = '#';  // Mark visited
// ... explore ...
board[i][j] = ch;   // Restore
// Benefit: Saves O(m*n) space

// OPTIMIZATION 4: Prune Trie nodes (advanced)
private void dfs(char[][] board, int i, int j, TrieNode parent, TrieNode node) {
    // ... after exploring all directions ...

    // If this node has no children and no word, remove it
    if (node.word == null && isEmpty(node)) {
        parent.children[board[i][j] - 'a'] = null;
    }
}

private boolean isEmpty(TrieNode node) {
    for (TrieNode child : node.children) {
        if (child != null) return false;
    }
    return true;
}

Analysis: - Time Complexity: O(m * n * 4^L) where mn = board size, L = max word length - Build Trie: O(w * k) where w = words, k = avg length - DFS: O(m * n * 4^L) - visit each cell, explore up to 4^L paths - Total dominated by DFS - Space Complexity: O(w * k) for Trie + O(L) for recursion stack - Pros: Optimal for this problem, scales well with many words - Cons:* More complex implementation

---

📝 Detailed Dry Run

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

Words: ["oath", "pea", "eat", "rain"]

PHASE 1: Build Trie

═══════════════════════════════════════════════
BUILD TRIE - INSERT ALL WORDS
═══════════════════════════════════════════════

Insert "oath":
  root → o → a → t → h (word = "oath")

Insert "pea":
  root → p → e → a (word = "pea")

Insert "eat":
  root → e → a → t (word = "eat")

Insert "rain":
  root → r → a → i → n (word = "rain")

Final Trie:
                    root
                 / | | \
                o  p e  r
                |  | |  |
                a  e a  a
                |  | |  |
                t  a t  i
                |       |
                h       n
           (oath) (pea) (eat) (rain)

Trie built! ✓
═══════════════════════════════════════════════

PHASE 2: DFS from Each Cell

═══════════════════════════════════════════════
DFS FROM (0,0) = 'o'
═══════════════════════════════════════════════

Start: i=0, j=0, ch='o', node=root

Check: root.children['o' - 'a'] exists? YES ✓
Move to node 'o'
Mark board[0][0] = '#'

Board state:
  #  a  a  n
  e  t  a  e
  i  h  k  r
  i  f  l  v

Try 4 directions from (0,0):

┌─────────────────────────────────────────────┐
│ Direction 1: UP (−1, 0) → Out of bounds    │
└─────────────────────────────────────────────┘

┌─────────────────────────────────────────────┐
│ Direction 2: DOWN (1, 0) = 'e'              │
├─────────────────────────────────────────────┤
│ Current node: 'o'                            │
│ Check: 'o'.children['e' - 'a'] exists?      │
│ NO! ✗                                        │
│ RETURN immediately (pruned!)                │
└─────────────────────────────────────────────┘

┌─────────────────────────────────────────────┐
│ Direction 3: LEFT (0, −1) → Out of bounds  │
└─────────────────────────────────────────────┘

┌─────────────────────────────────────────────┐
│ Direction 4: RIGHT (0, 1) = 'a'             │
├─────────────────────────────────────────────┤
│ Current node: 'o'                            │
│ Check: 'o'.children['a' - 'a'] exists?      │
│ YES! ✓                                       │
│ Move to node 'a' (under 'o')                │
│ Mark board[0][1] = '#'                      │
│                                              │
│ Board state:                                 │
│   #  #  a  n                                │
│   e  t  a  e                                │
│   i  h  k  r                                │
│   i  f  l  v                                │
│                                              │
│ Try 4 directions from (0,1):                │
│                                              │
│   UP (−1,1): Out of bounds                  │
│                                              │
│   DOWN (1,1) = 't':                         │
│     Current node: 'a' (under 'o')           │
│     Check: 'a'.children['t' - 'a']?         │
│     YES! ✓                                   │
│     Move to node 't'                         │
│     Mark board[1][1] = '#'                  │
│                                              │
│     Board state:                             │
│       #  #  a  n                            │
│       e  #  a  e                            │
│       i  h  k  r                            │
│       i  f  l  v                            │
│                                              │
│     Try 4 directions from (1,1):            │
│                                              │
│       UP (0,1): '#' → skip                  │
│                                              │
│       DOWN (2,1) = 'h':                     │
│         Current node: 't'                    │
│         Check: 't'.children['h' - 'a']?     │
│         YES! ✓                               │
│         Move to node 'h'                     │
│         node.word != null? YES!             │
│         Found "oath"! ✓✓✓                   │
│         Add to result                        │
│         Set node.word = null                │
│         Mark board[2][1] = '#'              │
│                                              │
│         Board state:                         │
│           #  #  a  n                        │
│           e  #  a  e                        │
│           i  #  k  r                        │
│           i  f  l  v                        │
│                                              │
│         Try 4 directions from (2,1):        │
│           (all return - no more words)      │
│                                              │
│         Backtrack: board[2][1] = 'h'        │
│                                              │
│       LEFT (1,0): '#' → skip                │
│       RIGHT (1,2) = 'a':                    │
│         't'.children['a']? NO ✗             │
│         Prune!                               │
│                                              │
│     Backtrack: board[1][1] = 't'            │
│                                              │
│   LEFT (0,0): '#' → skip                    │
│   RIGHT (0,2) = 'a':                        │
│     'a'.children['a']? NO ✗                 │
│     Prune!                                   │
│                                              │
│ Backtrack: board[0][1] = 'a'                │
└─────────────────────────────────────────────┘

Backtrack: board[0][0] = 'o'

═══════════════════════════════════════════════
DFS FROM (0,1) = 'a'
═══════════════════════════════════════════════

Start: i=0, j=1, ch='a', node=root

Check: root.children['a' - 'a'] exists? NO ✗
RETURN immediately (no words start with 'a')

═══════════════════════════════════════════════
DFS FROM (1,0) = 'e'
═══════════════════════════════════════════════

Start: i=1, j=0, ch='e', node=root

Check: root.children['e' - 'a'] exists? YES ✓
Move to node 'e'
Mark board[1][0] = '#'

Try 4 directions from (1,0):

┌─────────────────────────────────────────────┐
│ Direction: UP (0,0) = 'o'                   │
├─────────────────────────────────────────────┤
│ Current node: 'e'                            │
│ Check: 'e'.children['o' - 'a']? NO ✗        │
│ Prune!                                       │
└─────────────────────────────────────────────┘

┌─────────────────────────────────────────────┐
│ Direction: RIGHT (1,1) = 't'                │
├─────────────────────────────────────────────┤
│ Current node: 'e'                            │
│ Check: 'e'.children['t' - 'a']? NO ✗        │
│ Prune!                                       │
└─────────────────────────────────────────────┘

... (other directions also fail)

Backtrack: board[1][0] = 'e'

═══════════════════════════════════════════════
DFS FROM (1,3) = 'e'
═══════════════════════════════════════════════

Start: i=1, j=3, ch='e', node=root

Check: root.children['e' - 'a'] exists? YES ✓
Move to node 'e'
Mark board[1][3] = '#'

Try 4 directions from (1,3):

┌─────────────────────────────────────────────┐
│ Direction: LEFT (1,2) = 'a'                 │
├─────────────────────────────────────────────┤
│ Current node: 'e'                            │
│ Check: 'e'.children['a' - 'a'] exists?      │
│ YES! ✓                                       │
│ Move to node 'a' (under 'e')                │
│ Mark board[1][2] = '#'                      │
│                                              │
│ Try 4 directions from (1,2):                │
│                                              │
│   LEFT (1,1) = 't':                         │
│     Current node: 'a' (under 'e')           │
│     Check: 'a'.children['t' - 'a']?         │
│     YES! ✓                                   │
│     Move to node 't'                         │
│     node.word != null? YES!                 │
│     Found "eat"! ✓✓✓                        │
│     Add to result                            │
│     Set node.word = null                    │
│                                              │
│   (continue exploring other paths...)       │
│                                              │
│ Backtrack: board[1][2] = 'a'                │
└─────────────────────────────────────────────┘

Backtrack: board[1][3] = 'e'

═══════════════════════════════════════════════
... Continue DFS from remaining cells ...
═══════════════════════════════════════════════

No 'p' on board → "pea" not found
No valid path for "rain" → not found

═══════════════════════════════════════════════
FINAL RESULT: ["oath", "eat"]
═══════════════════════════════════════════════

Key Observations:

1. Trie guides the search
   - At each step, check if prefix exists in Trie
   - If not → prune immediately!
   - Saves massive computation

2. Found words marked as null
   - node.word = null after found
   - Prevents duplicate results
   - Same word not added twice

3. Board modified for visited tracking
   - board[i][j] = '#' when visiting
   - board[i][j] = original when backtracking
   - Saves O(m*n) space vs separate visited array

4. DFS from EVERY cell
   - Words can start anywhere
   - Each cell is a potential starting point
   - Trie prunes most explorations quickly

5. Multiple words found in ONE traversal
   - "oath" and "eat" both found
   - Don't need separate search per word
   - This is the KEY optimization! 🎯

---

📊 Complexity Analysis

Approach 2: Trie + Backtracking (Optimal)

Time Complexity:

w = number of words
k = average word length
m = board rows
n = board columns
L = maximum word length

Build Trie:
  - Insert w words
  - Each word: O(k) operations
  - Total: O(w * k)

DFS from each cell:
  - Start from m*n cells
  - Each DFS explores up to 4^L paths (4 directions, L depth)
  - BUT Trie prunes many paths early!
  - Worst case: O(m * n * 4^L)
  - Practical: Much better due to pruning

Overall: O(w * k + m * n * 4^L)

In practice:
  - Trie pruning is very effective
  - Most paths stop after 1-2 characters
  - Real performance much better than worst case! 🚀

Space Complexity:

Trie space:
  - O(w * k) for storing all words
  - In worst case (no shared prefixes)

DFS recursion stack:
  - O(L) maximum depth
  - L = longest word length

Board modification:
  - O(1) - modify in place
  - No separate visited array needed!

Overall: O(w * k + L) 📦

Space is very efficient:
  - No visited array needed
  - Trie shares common prefixes
  - Only recursion stack for DFS

Comparison with Brute Force:

┌──────────────────┬────────────────┬─────────────────┐
│    Approach      │  Time          │  Space          │
├──────────────────┼────────────────┼─────────────────┤
│ Brute Force      │ O(w*m*n*4^L)   │ O(L + m*n)      │
│ Trie+Backtrack   │ O(m*n*4^L)     │ O(w*k + L)      │
└──────────────────┴────────────────┴─────────────────┘

Key difference: Factor of 'w' eliminated!

For 30000 words: 30000x faster! 🚀

---

🎯 Pattern Recognition

Trie Pattern #5: Trie + Board Backtracking

┌──────────────────────────────────────────────────────┐
│   PATTERN 5: TRIE + BOARD BACKTRACKING               │
├──────────────────────────────────────────────────────┤
│ Use Case: Find multiple words on 2D board            │
│ Problems: 166 (Word Search II)                       │
│                                                       │
│ Key Components:                                       │
│   1. Trie: Pre-process dictionary                    │
│   2. Backtracking: Explore board exhaustively        │
│   3. Synergy: Trie guides and prunes backtracking    │
│                                                       │
│ Algorithm:                                            │
│   1. Build Trie with all words                       │
│   2. For each cell on board:                         │
│      - Start DFS with root of Trie                   │
│      - At each step:                                 │
│        * Check if Trie has this character            │
│        * If no → prune (stop exploring)              │
│        * If yes → continue to next level             │
│        * If word found → record it                   │
│   3. Try all 4 directions recursively                │
│   4. Backtrack: restore state                        │
│                                                       │
│ Critical Optimizations:                              │
│   • Store word at end nodes (avoid rebuilding)       │
│   • Set word to null after found (avoid duplicates)  │
│   • Modify board instead of visited array (space)    │
│   • Prune Trie nodes after use (advanced)            │
│                                                       │
│ Template:                                             │
│   dfs(board, i, j, trieNode):                        │
│       if (boundary check) return                     │
│       ch = board[i][j]                               │
│       if (ch == '#') return  # visited               │
│       if (!trieNode.children[ch]) return  # prune!   │
│       node = trieNode.children[ch]                   │
│       if (node.word) result.add(node.word)           │
│       board[i][j] = '#'                              │
│       dfs(all 4 directions, node)                    │
│       board[i][j] = ch  # backtrack                  │
└──────────────────────────────────────────────────────┘

This combines TWO classic patterns! 🎯

All Five Trie Patterns:

Pattern 1 (161): EXACT WORD SEARCH ✓
  • Dictionary lookup
  • Check at end only

Pattern 2 (162): WILDCARD SEARCH ✓
  • Pattern matching
  • Backtracking with wildcards

Pattern 3 (164): PREFIX SEARCH (SHORTEST) ✓
  • Root replacement
  • Check at each step, stop first

Pattern 4 (165): PREFIX CHAIN VALIDATION ✓
  • Incremental building
  • All ancestors must be valid

Pattern 5 (166): TRIE + BOARD BACKTRACKING ✓
  • Multiple word search on 2D board
  • Trie-guided exploration with pruning

Five patterns, five different problems! 🏆

Related Problems:

1. Word Search (79) - Single word on board
   Pattern: Backtracking only (no Trie)

2. Word Search II (212) - This problem!
   Pattern: Trie + Backtracking

3. Boggle Game - Find all words on board
   Pattern: Same as Word Search II

4. Word Squares (425)
   Pattern: Trie + Backtracking + Construction

5. Stream of Characters (1032)
   Pattern: Reversed Trie for suffix matching

Word Search II is THE classic Trie+Backtracking problem! 🎯

---

🔍 Common Mistakes

❌ Mistake 1: Using separate visited array

// WRONG! - Wastes O(m*n) space
boolean[][] visited = new boolean[m][n];

private void dfs(char[][] board, int i, int j, TrieNode node, boolean[][] visited) {
    visited[i][j] = true;
    // ... explore ...
    visited[i][j] = false;
}

// CORRECT! ✓ - Modify board in place
private void dfs(char[][] board, int i, int j, TrieNode node) {
    char ch = board[i][j];
    board[i][j] = '#';  // Mark visited
    // ... explore ...
    board[i][j] = ch;   // Restore
}

// Why better:
// - Saves O(m*n) space
// - Simpler code
// - Same functionality

❌ Mistake 2: Not preventing duplicate results

// WRONG! - Same word added multiple times
if (node.word != null) {
    result.add(node.word);
    // Continues exploring, might find same word again!
}

// CORRECT! ✓ - Set to null after found
if (node.word != null) {
    result.add(node.word);
    node.word = null;  // Prevent duplicates!
}

// Example: "aa" appears twice on board
// Without null: ["aa", "aa"] ✗
// With null: ["aa"] ✓

❌ Mistake 3: Not pruning early

// WRONG! - Explores even when prefix doesn't exist
private void dfs(char[][] board, int i, int j, TrieNode node) {
    // ... boundary checks ...

    char ch = board[i][j];
    // Missing check! Goes ahead blindly

    board[i][j] = '#';
    dfs(board, i-1, j, node);  // Explores without validation
    // ...
}

// CORRECT! ✓ - Check Trie first
private void dfs(char[][] board, int i, int j, TrieNode node) {
    // ... boundary checks ...

    char ch = board[i][j];
    int index = ch - 'a';

    // KEY: Check before exploring!
    if (node.children[index] == null) {
        return;  // Prune immediately!
    }

    node = node.children[index];

    board[i][j] = '#';
    dfs(board, i-1, j, node);
    // ...
}

// The difference:
// Without check: Explores all 4^L paths
// With check: Prunes invalid paths early
// MASSIVE performance difference! 🚀

❌ Mistake 4: Wrong Trie node progression

// WRONG! - Uses wrong node level
private void dfs(char[][] board, int i, int j, TrieNode node) {
    char ch = board[i][j];
    // ... checks ...

    board[i][j] = '#';

    // Uses SAME node for all directions - WRONG!
    dfs(board, i-1, j, node);
    dfs(board, i+1, j, node);
    dfs(board, i, j-1, node);
    dfs(board, i, j+1, node);

    board[i][j] = ch;
}

// CORRECT! ✓ - Advance to next Trie level
private void dfs(char[][] board, int i, int j, TrieNode node) {
    char ch = board[i][j];
    int index = ch - 'a';
    if (node.children[index] == null) return;

    // Advance to NEXT level!
    TrieNode nextNode = node.children[index];

    if (nextNode.word != null) {
        result.add(nextNode.word);
        nextNode.word = null;
    }

    board[i][j] = '#';

    // Pass NEXT node to children!
    dfs(board, i-1, j, nextNode);
    dfs(board, i+1, j, nextNode);
    dfs(board, i, j-1, nextNode);
    dfs(board, i, j+1, nextNode);

    board[i][j] = ch;
}

// The Trie node must advance with each step! 🔑

❌ Mistake 5: Incorrect boundary checks order

// WRONG! - Checks character before boundary
private void dfs(char[][] board, int i, int j, TrieNode node) {
    char ch = board[i][j];  // May crash if out of bounds!

    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
        return;
    }
    // ...
}

// CORRECT! ✓ - Check boundary first
private void dfs(char[][] board, int i, int j, TrieNode node) {
    // Boundary check FIRST!
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
        return;
    }

    char ch = board[i][j];  // Safe now
    // ...
}

---

📝 Quick Revision Notes

🎯 Core Concept

Word Search II combines Trie (dictionary pre-processing) with Backtracking (board exploration). Build Trie once O(wk), then DFS from each cell O(mn*4^L). Key optimization: Trie prunes invalid paths early - if no word has prefix, stop exploring! Store word at end nodes, set to null after found (avoid duplicates), modify board in place (save space). Multiple words found in single traversal - huge efficiency gain!

⚡ Quick Implementation

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class TrieNode {
  TrieNode[] children;
  boolean isEnd;
  String word; // saves the word when isEnd is true. Just for comfort and for some use case problem like // Longest word in dict

  public TrieNode() {
    // Just space allocated. All are NULLs.
    // For example, this.children[0] = null, this.children[1] = null and so on till this.children[25] = null
    // Why null? We will initialize with new TrieNode() only when character comes. Why unncessary space before char comes?
    // Check insert method. Only when character comes, we go and initialize that element in the array.
    // For binary numbers, you do need 26 (as its just 0 or 1). Also, isEnd is not required. 
    // But lets use the same for all problems to have it generic.
    this.children = new TrieNode[26];
    this.isEnd = false;
    this.word = null;
  }  
}

public class Solution {
  TrieNode root;

  public List<String> findWords(char[][] board, String[] words) {
    root = new TrieNode();
    Set<String> res = new HashSet<>(); // to avoid duplicates as asked in question. Else, list is also fine

    for(String word : words) {
      insert(word);
    }

    int rows = board.length;
    int cols = board[0].length;
    for(int i = 0; i < rows; i++) {
      for(int j = 0; j < cols; j++) {
        // Do DFS at every character by moving all directions and check if the word exists.
        dfs(i, j, board, res, root);
      }
    }

    return new ArrayList<>(res);
  }

  private void dfs(int i, int j, char[][] board, Set<String> res, TrieNode curr) {
    // check boundary before proceeding
    if(i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
      return;
    }

    // check if the incoming character exists in Trie
    char ch = board[i][j];
    if(ch == '#') { // already visited char
      return;
    }

    int index = ch - 'a';
    if(curr.children[index] == null) {
      return; // no char found. Return.
    }

    // Proceed with next child
    curr = curr.children[index];

    // Check if word is found. For this, you need to save the word while building Trie.
    if(curr.word != null) {
      res.add(curr.word);
    }

    // before moving in all directions. Mark it as visited to prevent looping    
    board[i][j] = '#';

    // now move in all directions.
    dfs(i + 1, j, board, res, curr); // next row, same col
    dfs(i - 1, j, board, res, curr); // prev row, same col
    dfs(i, j + 1, board, res, curr); // same row, next col
    dfs(i, j - 1, board, res, curr); // same row, prev col    

    // revert back that character
    board[i][j] = ch;
  }

  private void insert(String word) {
    TrieNode curr = root;
    for(char ch : word.toCharArray()) {
      int index = ch - 'a';

      if(curr.children[index] == null) {
        curr.children[index] = new TrieNode();
      }

      curr = curr.children[index];
    }

    curr.isEnd = true; // Not required actually for this problem as we are storing word itself in other field.
    curr.word = word; // CHANGE / EXTRA
  }

  public static void main(String[] args) {
        Solution s = new Solution();
    System.out.println(s.findWords(new char[][] {{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}}, new String[] {"oath","pea","eat","rain"}));
    System.out.println(s.findWords(new char[][] {{'o','a','b','n'},{'o','t','a','e'},{'a','h','k','r'},{'a','f','l','v'}}, new String[] {"oa","oaa"}));
    }
}

🔑 Key Insights

Why Trie + Backtracking:

Brute Force:
  For each word:
    For each cell:
      DFS to find word
  Time: O(w * m * n * 4^L)

Trie + Backtracking:
  Build Trie once
  For each cell:
    DFS guided by Trie
    Find ALL words in one pass
  Time: O(m * n * 4^L)

Eliminates factor of 'w'! 🚀

The Pruning Power:

Without Trie:
  Explores all 4^L paths from each cell
  Even for impossible words

With Trie:
  At each step: Check if prefix exists
  If no → STOP immediately
  Prunes most paths after 1-2 characters

Example: Board has no 'p'
  "pea" exploration stops at first step!
  Saves 4^7 = 16,384 explorations! 💨

The Three Key Optimizations:

// 1. Store word at end (no rebuild)
node.word = "oath";

// 2. Set to null after found (no duplicates)
if (node.word != null) {
    result.add(node.word);
    node.word = null;  // KEY!
}

// 3. Modify board in place (save space)
board[i][j] = '#';  // Mark visited
// ... explore ...
board[i][j] = ch;   // Restore

🎪 Memory Hooks

"Trie guides, Backtracking explores!"
"Check Trie before exploring - prune early!"
"One traversal, all words found!"
"Store word, mark null, modify board!" 🔥

⚠️ Don't Forget

• Build Trie FIRST (before any DFS)
• Check boundary conditions BEFORE accessing board
• Check if (node.children[idx] == null) to prune
• Advance Trie node with each DFS step (node = node.children[idx])
• Set node.word = null after adding to result
• Mark visited with board[i][j] = '#'
• Restore in backtrack board[i][j] = ch
• DFS from EVERY cell (words can start anywhere)

---

🎉 Congratulations!

You've mastered Trie + Backtracking - the ultimate combination!

What You Learned:

✅ Trie + Backtracking synergy - two patterns combined
✅ Early pruning - check Trie before exploring
✅ Board modification - space-efficient visited tracking
✅ Duplicate prevention - set word to null after found
✅ Multi-word discovery - find all words in one pass
✅ O(mn4^L) complexity - factor of w eliminated!

The Five Trie Patterns Complete:

Pattern 1 (161): EXACT WORD SEARCH ✓
  Basic Trie operations

Pattern 2 (162): WILDCARD SEARCH ✓
  Backtracking with wildcards

Pattern 3 (164): PREFIX SEARCH ✓
  Find shortest matching prefix

Pattern 4 (165): CHAIN VALIDATION ✓
  All prefixes must exist

Pattern 5 (166): TRIE + BOARD BACKTRACKING ✓
  Multi-word search on 2D board

Complete Trie mastery! 🏆✨

Interview Mastery:

Interviewer: "Find all words on board from dictionary"

Your response:
  "This is Word Search II - classic Trie + Backtracking!

   Problem analysis:
   - Brute force: Check each word separately
   - Time: O(w * m * n * 4^L) - too slow!

   Optimized approach:
   1. Build Trie with all dictionary words
   2. DFS from each board cell
   3. Trie guides exploration at each step

   Key optimizations:
   • Early pruning: If Trie has no prefix, stop!
   • One traversal: Find all words in single pass
   • Space efficient: Modify board for visited
   • No duplicates: Set word to null after found

   Algorithm:
   - Build Trie: O(w * k)
   - DFS from each cell with Trie guidance
   - At each step: check if char exists in Trie
   - If no → prune immediately!
   - If yes → continue to next Trie level
   - If word found → record and mark null

   Complexity:
   - Time: O(m * n * 4^L) vs O(w * m * n * 4^L)
   - Factor of 'w' eliminated!
   - Space: O(w * k) for Trie

   The key insight:
   - Trie prunes invalid paths EARLY
   - Multiple words found in ONE traversal
   - This is why Trie is perfect for this problem!

   For 30000 words: 30000x faster than brute force!"

Shows complete mastery! 💯

Your Complete Trie Journey:

Problem 161: Basic Trie ✓
  Foundation of Trie data structure

Problem 162: Wildcard Trie ✓
  Backtracking with pattern matching

Problem 163: Binary Trie ✓
  XOR optimization with 2 children

Problem 164: Prefix Search Trie ✓
  Find shortest matching prefix

Problem 165: Chain Validation Trie ✓
  Incremental building verification

Problem 166: Trie + Board Backtracking ✓
  Ultimate combination of two patterns

You're now a COMPLETE Trie expert! 🎯🏆✨

This is a HARD problem - be proud! 🚀

You've conquered all major Trie patterns! Incredible work! 🎊