LeetCode Solution 212 - Word Search II

Problem Statement

Given an m x n board of characters and a list of words from the dictionary, find all words in 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:

Input:

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

Output:

["oath","eat"]

---

Optimal Approach: Trie + Backtracking

Why Trie?

• Using a Trie reduces redundant lookups.
• Efficiently matches prefixes, reducing unnecessary DFS calls.
• Helps prune paths that don’t lead to valid words.

Algorithm:

1. Insert all words into a Trie.
2. Perform DFS (backtracking) for each cell in the grid.
3. If a prefix exists in the Trie, continue searching.
4. If a word is found, add it to the result and mark it as found.
5. Use a visited flag to avoid revisiting cells in the current path.

---

C++ Code Implementation

class Solution {
public:
    struct TrieNode {
        unordered_map<char, TrieNode*> children;
        string word;
    };
    
    void insertWord(TrieNode* root, const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children.count(c)) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->word = word;
    }
    
    void dfs(vector<vector<char>>& board, int i, int j, TrieNode* node, vector<string>& result) {
        char c = board[i][j];
        if (!node->children.count(c)) return;
        node = node->children[c];
        if (!node->word.empty()) {
            result.push_back(node->word);
            node->word.clear(); // Avoid duplicates
        }
        
        board[i][j] = '#';
        vector<pair<int, int>> directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        for (auto [dx, dy] : directions) {
            int x = i + dx, y = j + dy;
            if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && board[x][y] != '#') {
                dfs(board, x, y, node, result);
            }
        }
        board[i][j] = c;
    }
    
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        TrieNode* root = new TrieNode();
        for (const string& word : words) insertWord(root, word);
        
        vector<string> result;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                dfs(board, i, j, root, result);
            }
        }
        return result;
    }
};

---

Step-by-Step Explanation

1. Building the Trie: Each word is inserted into the Trie, allowing for efficient prefix lookup.
2. DFS Traversal: For each cell, we explore possible words using backtracking.
3. Tracking Words Found: When we reach a word in the Trie, we add it to the result and mark it as used.
4. Backtracking: We revert visited cells to their original state after exploring all paths.

---

Dry Run

Input:

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

Execution:

• Insert words into Trie.
• Start DFS from each cell:
  • "o" → "a" → "t" → "h" → found "oath".
  • "e" → "a" → "t" → found "eat".
• Return {"oath", "eat"}.

---

Alternative Approaches

Approach	Time Complexity	Space Complexity	Reason for Rejection
Brute Force (Check each word in grid)	O(W * M * N * 4^L)	O(1)	Too slow, redundant checks
Trie + DFS (Backtracking)	O(M * N * 4^L)	O(W * L)	Most optimal
DP	Not feasible	-	Not applicable for word search

---

Complexity Analysis

• Time Complexity: O(M * N * 4^L), where M, N are board dimensions, and L is word length.
• Space Complexity: O(W * L) for the Trie.

---

Conclusion

• Best Approach: Trie + DFS (Backtracking) balances efficiency and simplicity.
• Further Practice:
  • Word Search I
  • Prefix Trie

This solution efficiently finds all words in the grid using Trie + Backtracking, making it optimal for large inputs.