Analysis and Failure

The time complexity of this approach is roughly $O(K \cdot M \cdot N \cdot 4^L)$, where:

• $K$ is the number of words.
• $M \times N$ is the grid size.
• $L$ is the maximum length of a word.

Why it fails: While this logic is correct, it results in a Time Limit Exceeded (TLE) error. The constraints state that words can contain up to $3 \times 10^4$ strings. If many words share common prefixes (e.g., "apple", "app", "application"), the brute force approach redundantly traverses the same grid paths for each word, leading to massive inefficiency.

Core Insight for Word Search II

The key to optimizing the LeetCode 212 solution is to invert the search process. Instead of iterating through the dictionary and searching the grid for each word, we iterate through the grid once and search the dictionary.

To do this efficiently, we need a data structure that allows us to search for multiple words simultaneously. The Trie (Prefix Tree) is the perfect candidate.

By inserting all candidate words into a Trie, we merge common prefixes. As we backtrack through the grid, we also traverse the Trie.

1. Synchronization: If we are at grid cell $(r, c)$ with character 'a', we check if the current Trie node has a child 'a'.
2. Pruning: If the Trie node does not have the required child, we stop exploring that path immediately (pruning the recursion tree).
3. Completion: If we reach a Trie node marked as the end of a word, we have found a valid word on the board.

Visual Description: Imagine the recursion tree overlaying the grid. At the root, we can move to any cell. Once we pick a cell (e.g., 'a'), we look at the Trie's root. If the Trie has an edge 'a', we step into that Trie node. We then look at neighbors in the grid. If a neighbor is 'n', we check if the current Trie node has an 'n' child. If yes, we proceed. If no, we backtrack. This effectively creates a "tunnel" where the grid path must fit inside the Trie structure.

Execution Flow

Let's assume words = ["oa", "oath"] and the board starts with [['o', 'a', ...], ...].

1. Setup: Build Trie with "oa" and "oath".
2. Start: Loop finds 'o' at (0,0). Call DFS(0, 0, root).
3. Step 1: board[0][0] is 'o'. Root has child 'o'. Move Trie pointer to node 'o'. Mark (0,0) as visited.
4. Step 2: Explore neighbors. Go right to (0,1) which is 'a'.
5. Step 3: board[0][1] is 'a'. Trie node 'o' has child 'a'. Move Trie pointer to node 'a'. Mark (0,1) as visited.
6. Match: Node 'a' marks end of word "oa". Add "oa" to results.
7. Step 4: Explore neighbors of (0,1). Suppose we find 't'.
8. Step 5: Trie node 'a' has child 't'. Move pointer. Continue until "oath" is found.
9. Backtrack: When recursion returns, unmark cells (0,1) and (0,0) so they can be used for paths starting elsewhere.

Proof of Correctness

The algorithm is correct because it exhaustively explores all valid paths on the grid that correspond to prefixes in the Trie.

• Completeness: By starting a DFS from every cell, we ensure no potential starting letter is missed.
• Constraints: The visited logic (modifying the board) ensures no cell is used twice in a single word.
• Validity: The Trie structure enforces that we only traverse paths forming valid dictionary words.
• Termination: The recursion depth is bounded by the number of cells (and practically by the max word length), ensuring the algorithm terminates.

Reference Implementation

C++ Solution for LeetCode 212

cpp
#include <vector>
#include <string>

using namespace std;

class Solution {
    struct TrieNode {
        TrieNode* children[26] = {nullptr};
        string* word = nullptr; // Pointer to string if this node ends a word
        
        ~TrieNode() {
            for (auto child : children) {
                if (child) delete child;
            }
        }
    };

    void insert(TrieNode* root, string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
        node->word = &word;
    }

    void backtrack(vector<vector<char>>& board, int r, int c, TrieNode* node, vector<string>& result) {
        char letter = board[r][c];
        int idx = letter - 'a';

        // If no child exists for this letter, stop (Pruning)
        if (!node->children[idx]) return;

        TrieNode* childNode = node->children[idx];

        // Check if we found a word
        if (childNode->word) {
            result.push_back(*childNode->word);
            childNode->word = nullptr; // Avoid duplicates
        }

        // Mark as visited
        board[r][c] = '#';

        // Explore neighbors
        int rowOffsets[] = {-1, 1, 0, 0};
        int colOffsets[] = {0, 0, -1, 1};

        for (int i = 0; i < 4; ++i) {
            int newRow = r + rowOffsets[i];
            int newCol = c + colOffsets[i];

            if (newRow >= 0 && newRow < board.size() && 
                newCol >= 0 && newCol < board[0].size() && 
                board[newRow][newCol] != '#') {
                backtrack(board, newRow, newCol, childNode, result);
            }
        }

        // Backtrack: Restore cell
        board[r][c] = letter;
    }

public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        TrieNode* root = new TrieNode();
        for (string& w : words) {
            insert(root, w);
        }

        vector<string> result;
        for (int r = 0; r < board.size(); ++r) {
            for (int c = 0; c < board[0].size(); ++c) {
                backtrack(board, r, c, root, result);
            }
        }
        
        // Clean up memory (optional for LeetCode but good practice)
        // delete root; // This would trigger recursive deletion
        return result;
    }
};

Java Solution for LeetCode 212

java
import java.util.*;

class Solution {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word = null;
    }

    public List<String> findWords(char[][] board, String[] words) {
        // 1. Build Trie
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode node = root;
            for (char c : w.toCharArray()) {
                int idx = c - 'a';
                if (node.children[idx] == null) {
                    node.children[idx] = new TrieNode();
                }
                node = node.children[idx];
            }
            node.word = w;
        }

        List<String> result = new ArrayList<>();
        
        // 2. Traverse Grid
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                if (root.children[board[r][c] - 'a'] != null) {
                    backtrack(board, r, c, root, result);
                }
            }
        }
        
        return result;
    }

    private void backtrack(char[][] board, int r, int c, TrieNode parent, List<String> result) {
        char letter = board[r][c];
        TrieNode currNode = parent.children[letter - 'a'];

        // Check if a word ends here
        if (currNode.word != null) {
            result.add(currNode.word);
            currNode.word = null; // Avoid duplicates
        }

        // Mark visited
        board[r][c] = '#';

        int[] dRow = {-1, 1, 0, 0};
        int[] dCol = {0, 0, -1, 1};

        for (int i = 0; i < 4; i++) {
            int newRow = r + dRow[i];
            int newCol = c + dCol[i];

            if (newRow >= 0 && newRow < board.length && 
                newCol >= 0 && newCol < board[0].length && 
                board[newRow][newCol] != '#') {
                
                if (currNode.children[board[newRow][newCol] - 'a'] != null) {
                    backtrack(board, newRow, newCol, currNode, result);
                }
            }
        }

        // Backtrack
        board[r][c] = letter;
    }
}

Python Solution for LeetCode 212

python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        # Build Trie
        root = TrieNode()
        for word in words:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.word = word

        result = []
        rows, cols = len(board), len(board[0])

        def backtrack(r, c, parent_node):
            char = board[r][c]
            curr_node = parent_node.children[char]

            # Check if we found a word
            if curr_node.word:
                result.append(curr_node.word)
                curr_node.word = None  # Avoid duplicates

            # Mark visited
            board[r][c] = '#'

            # Explore neighbors
            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    if board[nr][nc] in curr_node.children:
                        backtrack(nr, nc, curr_node)

            # Backtrack
            board[r][c] = char
            
            # Optimization: prune leaf nodes to speed up future searches
            if not curr_node.children:
                del parent_node.children[char]

        for r in range(rows):
            for c in range(cols):
                if board[r][c] in root.children:
                    backtrack(r, c, root)

        return result