Problem Statement

You are given an m x n board of characters and a list of strings called words.
Return all the words that can be formed by tracing adjacent letters on the board.

Each letter cell may be used only once per word, and words must be formed from horizontally or vertically adjacent cells.

---

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

• 1 <= m, n <= 12
• board[i][j] is a lowercase English letter.
• 1 <= words.length <= 3 * 10^4
• 1 <= words[i].length <= 10
• All words in words are unique.

---

Intuition and Key Idea

The brute-force approach — searching every word individually using DFS — becomes inefficient because there can be up to 30,000 words.

Instead, we can use a Trie (prefix tree) to efficiently store all the words and search them simultaneously while exploring the grid.

The Trie helps us:

• Quickly reject paths that can’t lead to a valid word.
• Detect valid words as soon as we reach them in DFS traversal.

This combination of Trie + DFS drastically improves performance.

---

Approach

1. Build a Trie

• Insert all words from the list into a Trie.
• Each Trie node represents one letter.
• Mark nodes that represent the end of a word.

2. Depth-First Search (DFS)

• Start DFS from every cell in the board.
• Explore 4 directions (up, down, left, right).
• Use a visited marker or temporarily modify the board to avoid revisiting cells.
• At each step:
  • Check if the current character exists as a child node in the Trie.
  • If yes, continue exploring.
  • If we reach a node that represents a complete word, add it to the result.
  • Remove duplicates by marking found words as null in the Trie.

3. Optimization

• To prevent redundant searches, prune branches that no longer match any word prefix.
• Modify the board in-place (board[i][j] = '#') to mark visited cells.

---

Java Implementation

import java.util.*;

public class WordSearchII {

    class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        String word = null; // Store word when end node is reached
    }

    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            for (char ch : word.toCharArray()) {
                node = node.children.computeIfAbsent(ch, k -> new TrieNode());
            }
            node.word = word; // mark the end of the word
        }
        return root;
    }

    private void dfs(char[][] board, int i, int j, TrieNode node, List<String> result) {
        char c = board[i][j];
        TrieNode nextNode = node.children.get(c);
        if (nextNode == null) return;

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

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

        int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
        for (int[] dir : directions) {
            int newRow = i + dir[0];
            int newCol = j + dir[1];
            if (newRow >= 0 && newRow < board.length && newCol >= 0 && newCol < board[0].length
                    && board[newRow][newCol] != '#') {
                dfs(board, newRow, newCol, nextNode, result);
            }
        }

        board[i][j] = c; // restore letter after exploring

        // Optimization: prune empty branches
        if (nextNode.children.isEmpty()) {
            node.children.remove(c);
        }
    }

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

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root, result);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        WordSearchII solver = new WordSearchII();

        char[][] board = {
            {'o','a','a','n'},
            {'e','t','a','e'},
            {'i','h','k','r'},
            {'i','f','l','v'}
        };
        String[] words = {"oath","pea","eat","rain"};

        System.out.println(solver.findWords(board, words)); // Output: [oath, eat]
    }
}

---

Step-by-Step Example

Let’s consider:

board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

1. Trie Construction
   • Root → o → a → t → h (end)
   • Root → e → a → t (end)
   • Root → p → e → a (end)
   • Root → r → a → i → n (end)
2. DFS begins at (0,0) = ‘o’
   • Matches start of “oath”
   • Continue to ‘a’ → ‘t’ → ‘h’
   • Found “oath”, add to result.
3. DFS from (1,1) = ‘t’ finds “eat”.
4. No valid path found for “pea” or “rain”.

Result = ["oath", "eat"]

---

Time and Space Complexity

Operation	Complexity	Explanation
Trie Construction	O(S)	S = sum of all characters in words
DFS Traversal	O(M × N × 4^L)	M×N grid, L = max word length
Space Complexity	O(S + M×N)	Trie + recursion stack

This is efficient given constraints since pruning cuts off most unneeded branches early.

---

Key Takeaways

1. Trie + DFS is the key to handling large word lists efficiently.
2. Pruning branches in the Trie avoids redundant computation.
3. Each word is added only once by marking found words as null.
4. This problem tests your ability to combine graph traversal with string prefix optimization.