LeetCode Word Search II：Trie 字典樹 + DFS 剪枝優化

題目

給定 m×n 字母板、字典 words，找出所有能在板上由相鄰格子（上下左右）順序組成的單詞。同一格子單詞中不可重複使用。返回列表（順序不限）。

解法：Trie + DFS

1. 將 words 插入 Trie，每節點存 26 子指針 + isEnd + word（終點存完整單詞）。
2. 板上每個格子作為起點 DFS：

• 若當前字符不在 Trie 當前節點的子樹 → 剪枝返回。
• 移動到子節點，標記板上格子已訪問（如置 '#'）。
• 若節點 isEnd，將 word 加入結果，**並清除 isEnd 避免重複加入**。
• 遞歸四方向，回溯恢復格子字符。

優化版代碼（48-56ms）

class TrieNode {
public:
    TrieNode* next[26];
    string word;
    TrieNode() { fill_n(next, 26, nullptr); word = ""; }
    ~TrieNode() { for (auto p : next) delete p; }
};

class Solution {
    int m, n;
    vector ans;
public:
    vector findWords(vector>& board, vector& words) {
        TrieNode* root = new TrieNode();
        for (auto& w : words) {
            TrieNode* cur = root;
            for (char c : w) {
                int idx = c - 'a';
                if (!cur->next[idx]) cur->next[idx] = new TrieNode();
                cur = cur->next[idx];
            }
            cur->word = w; // 終點存單詞
        }
        m = board.size(); n = board[0].size();
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                dfs(board, root, i, j);
        delete root;
        return ans;
    }
    void dfs(vector>& board, TrieNode* node, int x, int y) {
        char c = board[x][y];
        if (c == '#' || !node->next[c-'a']) return;
        node = node->next[c-'a'];
        if (!node->word.empty()) {
            ans.push_back(node->word);
            node->word.clear(); // 去重
        }
        board[x][y] = '#';
        if (x > 0) dfs(board, node, x-1, y);
        if (x+1 < m) dfs(board, node, x+1, y);
        if (y > 0) dfs(board, node, x, y-1);
        if (y+1 < n) dfs(board, node, x, y+1);
        board[x][y] = c;
    }
};

複雜度

• 構建 Trie：O(Σ|w|)。
• DFS：每個格子最多進入 Trie 深度為最長單詞長度，剪枝極強，實測 O(m×n×4^L) 但常數極小。
• 空間：Trie 節點數 O(Σ|w|)。

關鍵優化點

1. Trie 節點存 word 而非 bool，找到即取詞並清空，天然去重無需 set。
2. 原地修改 board 標記訪問，省去 visited 數組。
3. 析構函數遞歸釋放 Trie 記憶體。