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.

1. Trie with DFS

Build a trie from the given words. Then, for each cell in the board, initiate a DFS to traverse the board while matching against the trie. When a word endpoint is found in the trie, add it to the result list and remove the word from the trie to avoid duplicates.

Key Optimization:

• Pass the board as a reference to the DFS function to avoid copying overhead.
• Use a global board variable to further reduce parameter passing.

class Trie {
public:
    string word;
    unordered_map<char, Trie*> children;
    Trie() : word("") {}
    void addWord(const string& w) {
        Trie* node = this;
        for (char ch : w) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->word = w;
    }
};

class Solution {
public:
    vector<string> result;
    vector<vector<char>> grid;
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    void dfs(int r, int c, Trie* node) {
        char ch = grid[r][c];
        if (node->children.find(ch) == node->children.end()) return;
        node = node->children[ch];
        if (!node->word.empty()) {
            result.push_back(node->word);
            node->word.clear();
        }
        grid[r][c] = '#';
        for (auto& dir : dirs) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr >= 0 && nr < grid.size() && nc >= 0 && nc < grid[0].size() && grid[nr][nc] != '#') {
                dfs(nr, nc, node);
            }
        }
        grid[r][c] = ch;
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        Trie* root = new Trie();
        for (auto& w : words) root->addWord(w);
        grid = board;
        int rows = board.size(), cols = board[0].size();
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                dfs(i, j, root);
            }
        }
        return result;
    }
};

2. HashSet with DFS

Store all words in an unordered_set. For each cell, perform a DFS up to depth 10 (maximum word length). If the constructed string exists in the set, add it to results and remove it from the set.

Performance Notes:

• Time complexity is moderate, but space usage is excellent.
• Passing the board by reference is critical to avoid timeouts.

class Solution {
public:
    unordered_set<string> wordSet;
    vector<string> foundWords;
    int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    void search(vector<vector<char>>& board, int r, int c, string current) {
        if (wordSet.find(current) != wordSet.end()) {
            foundWords.push_back(current);
            wordSet.erase(current);
        }
        if (current.length() == 10) return;
        char original = board[r][c];
        board[r][c] = '#';
        for (auto& dir : directions) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr >= 0 && nr < board.size() && nc >= 0 && nc < board[0].size() && board[nr][nc] != '#') {
                search(board, nr, nc, current + board[nr][nc]);
            }
        }
        board[r][c] = original;
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        wordSet.insert(words.begin(), words.end());
        int rows = board.size(), cols = board[0].size();
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                search(board, i, j, string(1, board[i][j]));
            }
        }
        return foundWords;
    }
};

3. Pruned DFS with Character Indexing

Preprocess the board to map each character to its positions. For each word, check if all its characters exist on the board. If so, attempt to find the word via DFS starting from positions matching the first character.

Key Optimizations:

• Early termination if a word contains a character not present on the board.
• For words with repeated leading characters (e.g., "aaaab"), reverse the word to reduce the number of starting positions.

class Solution {
public:
    bool dfs(vector<vector<char>>& board, int r, int c, const string& target, int pos) {
        if (pos == target.length() - 1) return true;
        char temp = board[r][c];
        board[r][c] = 0;
        char nextChar = target[pos + 1];
        bool found = false;
        if (r > 0 && board[r-1][c] == nextChar && dfs(board, r-1, c, target, pos+1)) found = true;
        if (!found && r+1 < board.size() && board[r+1][c] == nextChar && dfs(board, r+1, c, target, pos+1)) found = true;
        if (!found && c > 0 && board[r][c-1] == nextChar && dfs(board, r, c-1, target, pos+1)) found = true;
        if (!found && c+1 < board[0].size() && board[r][c+1] == nextChar && dfs(board, r, c+1, target, pos+1)) found = true;
        board[r][c] = temp;
        return found;
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> result;
        unordered_map<char, vector<pair<int, int>>> positions;
        int rows = board.size(), cols = board[0].size();
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                positions[board[i][j]].emplace_back(i, j);
            }
        }
        for (auto& w : words) {
            bool skip = false;
            for (char ch : w) {
                if (positions.find(ch) == positions.end()) {
                    skip = true;
                    break;
                }
            }
            if (skip) continue;
            string searchWord = w;
            if (w.length() > 5 && w[0] == w[1] && w[1] == w[2] && w[2] == w[3]) {
                reverse(searchWord.begin(), searchWord.end());
            }
            for (auto& [r, c] : positions[searchWord[0]]) {
                if (dfs(board, r, c, searchWord, 0)) {
                    result.push_back(w);
                    break;
                }
            }
        }
        return result;
    }
};

4. Trie with Pruning and Indexing

Combine trie and pruning: build a trie from words, then for each starting character, traverse the board from corresponding positions to match the trie. Remove matched words and prune leaf nodes from the trie during traversal.

Performance Characteristics:

• Time performance is excellent, similar to solution 3.
• Space usage is higher due to the trie structure.

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    string word;
    TrieNode* addWord(const string& w) {
        TrieNode* node = this;
        for (char ch : w) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        return node;
    }
};

class Solution {
public:
    vector<string> result;
    bool dfs(vector<vector<char>>& board, int r, int c, TrieNode* node) {
        if (!node->word.empty()) {
            result.push_back(node->word);
            node->word.clear();
        }
        if (node->children.empty()) return true;
        char original = board[r][c];
        board[r][c] = 0;
        bool allMatched = true;
        for (auto it = node->children.begin(); it != node->children.end(); ) {
            char ch = it->first;
            TrieNode* child = it->second;
            bool found = false;
            if (r > 0 && board[r-1][c] == ch && dfs(board, r-1, c, child)) found = true;
            if (!found && r+1 < board.size() && board[r+1][c] == ch && dfs(board, r+1, c, child)) found = true;
            if (!found && c > 0 && board[r][c-1] == ch && dfs(board, r, c-1, child)) found = true;
            if (!found && c+1 < board[0].size() && board[r][c+1] == ch && dfs(board, r, c+1, child)) found = true;
            if (found) {
                it = node->children.erase(it);
                continue;
            }
            allMatched = false;
            ++it;
        }
        board[r][c] = original;
        return allMatched;
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        unordered_map<char, vector<pair<int, int>>> charPositions;
        int rows = board.size(), cols = board[0].size();
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                charPositions[board[i][j]].emplace_back(i, j);
            }
        }
        TrieNode* root = new TrieNode();
        for (auto& w : words) {
            bool valid = true;
            for (char ch : w) {
                if (charPositions.find(ch) == charPositions.end()) {
                    valid = false;
                    break;
                }
            }
            if (!valid) continue;
            string processed = w;
            if (w.length() > 5 && w[0] == w[1] && w[1] == w[2] && w[2] == w[3]) {
                reverse(processed.begin(), processed.end());
            }
            (root->addWord(processed))->word = w;
        }
        for (auto& [ch, positions] : charPositions) {
            auto it = root->children.find(ch);
            if (it == root->children.end()) continue;
            for (auto& [r, c] : positions) {
                if (dfs(board, r, c, it->second)) break;
            }
        }
        return result;
    }
};