Word Search II

How it works

We still do DFS on the board, but we guide the DFS using a Trie so we only walk paths that match prefixes of the given words.

This version is faster because it adds aggressive pruning:

• Each Trie node keeps refs = "how many words in the dictionary still pass through this node".
• When we successfully find one or more words, each DFS call returns how many new words it found below its current prefix.
• We subtract that count from refs as DFS unwinds, removing the found words from every Trie node on their paths.
• If after removal a node's refs becomes 0, that branch is dead (no remaining words use it), so we physically cut the pointer from its parent (prev.children[...] = null). That prevents future DFS calls from exploring useless prefixes.

Also, instead of using a visited set, we mark the board in-place:

• Temporarily set board[r][c] = '*' while exploring that path.
• Restore it when backtracking.

What the Trie stores

Each node has:

• children[26]: next letters (array, faster than hashmap)
• idx: index of a word in words if a word ends here, else -1
• refs: number of “still-alive” words that go through this node (including end words)

Steps

1. Build the Trie:

   • Insert every word words[i].
   • While inserting, increment refs on every node along the path.
   • At the end node, store idx = i.

2. DFS from every board cell:

   • dfs(r, c, node) tries to extend the current Trie path using board[r][c].

3. DFS rules:

   • Stop if:
     • out of bounds, or
     • cell is already used in current path ('*'), or
     • Trie has no child for board[r][c]
   • Otherwise:
     1. Take letter ch = board[r][c], move to child = node.children[ch]
     2. Mark cell as visited: board[r][c] = '*'
     3. If child.idx != -1, we found a word:
        • add words[child.idx] to result
        • set child.idx = -1 (avoid duplicates)
        • initialize found = 1
     4. Recurse into 4 neighbors with child, adding their returned counts to found
     5. Decrease child.refs by found
     6. If child.refs == 0, cut this branch from its parent:
        • node.children[ch] = null
     7. Restore the board cell and return found so every ancestor can update its own refs

4. After each top-level DFS, decrease root.refs by the returned count.

5. Return collected results.

Complexity

• Time complexity: O(m * n * 4 * 3 ^ {t - 1} + s)
• Space complexity: O(s)

Where m is the number of rows, n is the number of columns, t is the maximum length of any word in the array words and s is the sum of the lengths of all the words.

Things to watch for

Forgetting to Remove Duplicate Words from Results

When multiple paths on the board can form the same word, adding the word to the result list without checking for duplicates leads to duplicate entries. Using a set for results or marking words as found in the Trie (by setting idx = -1 or isWord = false) prevents this issue.

Not Restoring the Board After Backtracking

When marking cells as visited by modifying the board directly (e.g., setting board[r][c] = '*'), forgetting to restore the original character after the recursive calls will corrupt the board state. This prevents other starting positions or words from finding valid paths.

Inefficient Trie Without Pruning

Building a Trie but not pruning it after finding words leads to repeated exploration of dead branches. Without decrementing refs counts and removing nodes when refs reaches zero, the algorithm continues searching paths that cannot yield any new words, significantly degrading performance.

Incorrect Trie Traversal During DFS

Advancing the Trie pointer before checking if the child node exists can cause null pointer exceptions. Always verify that node.children[char] exists before moving to the next node. Similarly, checking isWord before updating the node pointer will miss the current word.

Not Handling the Visited Set Correctly with Trie

When using a separate visited set alongside the Trie, forgetting to clear or properly backtrack the visited set for each new starting cell can block valid paths. Each DFS starting point should begin with a fresh or properly reset visited state.

from typing import List

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.idx = -1
        self.refs = 0

    def addWord(self, word, i):
        cur = self
        cur.refs += 1
        for c in word:
            index = ord(c) - ord('a')
            if not cur.children[index]:
                cur.children[index] = TrieNode()
            cur = cur.children[index]
            cur.refs += 1
        cur.idx = i

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()
        for i in range(len(words)):
            root.addWord(words[i], i)

        ROWS, COLS = len(board), len(board[0])
        res = []

        def getIndex(c):
            index = ord(c) - ord('a')
            return index

        def dfs(r, c, node):
            if (r < 0 or c < 0 or r >= ROWS or
                c >= COLS or board[r][c] == '*' or
                not node.children[getIndex(board[r][c])]):
                return 0

            tmp = board[r][c]
            board[r][c] = '*'
            prev = node
            node = node.children[getIndex(tmp)]
            found = 0
            if node.idx != -1:
                res.append(words[node.idx])
                node.idx = -1
                found += 1

            found += dfs(r + 1, c, node)
            found += dfs(r - 1, c, node)
            found += dfs(r, c + 1, node)
            found += dfs(r, c - 1, node)

            board[r][c] = tmp
            node.refs -= found
            if not node.refs:
                prev.children[getIndex(tmp)] = None
            return found

        for r in range(ROWS):
            for c in range(COLS):
                root.refs -= dfs(r, c, root)

        return res

class TrieNode {
public:
    TrieNode* children[26];
    int idx;
    int refs;

    TrieNode() {
        for (int i = 0; i < 26; ++i) {
            children[i] = nullptr;
        }
        idx = -1;
        refs = 0;
    }

    void addWord(const string& word, int i) {
        TrieNode* cur = this;
        cur->refs++;
        for (char c : word) {
            int index = c - 'a';
            if (!cur->children[index]) {
                cur->children[index] = new TrieNode();
            }
            cur = cur->children[index];
            cur->refs++;
        }
        cur->idx = i;
    }
};

class Solution {
public:
    vector<string> res;

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        TrieNode* root = new TrieNode();
        for (int i = 0; i < words.size(); ++i) {
            root->addWord(words[i], i);
        }

        for (int r = 0; r < board.size(); ++r) {
            for (int c = 0; c < board[0].size(); ++c) {
                root->refs -= dfs(board, root, r, c, words);
            }
        }

        return res;
    }

    int dfs(auto& board, TrieNode* node, int r, int c, auto& words) {
        if (r < 0 || c < 0 || r >= board.size() ||
            c >= board[0].size() || board[r][c] == '*' ||
            !node->children[board[r][c] - 'a']) {
            return 0;
        }

        char temp = board[r][c];
        board[r][c] = '*';
        TrieNode* prev = node;
        node = node->children[temp - 'a'];
        int found = 0;
        if (node->idx != -1) {
            res.push_back(words[node->idx]);
            node->idx = -1;
            found++;
        }

        found += dfs(board, node, r + 1, c, words);
        found += dfs(board, node, r - 1, c, words);
        found += dfs(board, node, r, c + 1, words);
        found += dfs(board, node, r, c - 1, words);

        board[r][c] = temp;
        node->refs -= found;
        if (!node->refs) {
            prev->children[temp - 'a'] = nullptr;
        }
        return found;
    }
};