212. 單字搜索 II

推薦事前閱讀：前綴樹/字典樹

思路

我們可以建立一個前綴樹來幫助搜索。

1. 先把要找的單字組合成前綴樹，pass紀錄經過的單字，end此時紀錄單字，後面搜索時，走到這個節點的時候，就把end記錄的單字加到答案中。
2. 搜索時每個節點都能作為起點，需要從每個點開始往外搜索。
3. 若有搜索到對應的單字，將pass變數減少，讓後面的搜索範圍減少。
4. 把走過的路標記為走訪過，在遞迴呼叫回傳之前，還原一開始的樣子，以供上層遞迴繼續往下呼叫。

程式碼

1. 類別實現

struct TrieNode {
    int pass;
    string end;
    array<TrieNode*, 26> nexts;
    TrieNode() : pass(0), nexts{nullptr} {}
};

class Trie {
public:
    TrieNode* root;
    Trie() : root(new TrieNode()) {}
    void buildTrie(vector<string>& words) {
        for(string s : words) {
            // 插入新的節點
            TrieNode* cur = root;
            for(char ch : s) {
                int path = ch - 'a';
                if(cur->nexts[path] == nullptr) {
                    cur->nexts[path] = new TrieNode();
                }
                cur = cur->nexts[path];
                cur->pass++;
            }
            cur->end = s; // 結尾紀錄字串，在查找時如果走訪到這裡，代表收集到了這個單字。
        }
    }

    // i, j: 當前在 board 的位置, cur: 當前在前綴樹的位置, res: 答案
    // return 收集到的節點數量，用於剪枝
    int dfs(vector<vector<char>>& board, int i, int j, TrieNode* cur, vector<string>& res) {
        if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] == 0) { // 邊界 + 走訪判斷
            return 0;
        }
        
        char temp = board[i][j];
        int path = temp - 'a';

        cur = cur->nexts[path]; // 前往下一個節點
        if(cur == nullptr || cur->pass == 0) { // 無路可走，或是下面的單字都已經被收集
            return 0;
        }

        int collected = 0;
        if(!cur->end.empty()) {
            collected++;
            res.push_back(cur->end);
            cur->end.clear();
        }

        board[i][j] = 0; // 標記為走訪過
        collected += dfs(board, i + 1, j, cur, res);
        collected += dfs(board, i - 1, j, cur, res);
        collected += dfs(board, i, j + 1, cur, res);
        collected += dfs(board, i, j - 1, cur, res);
        board[i][j] = temp; // 還原現場
        cur->pass -= collected;
        return collected;
    }
};

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        Trie trie;
        trie.buildTrie(words);
        
        int n = board.size(), m = board[0].size();
        vector<string> res;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                trie.dfs(board, i, j, trie.root, res);
            }
        }
        return res;
    }
};

2. 靜態數組實現

const int MX = 10001;
int trie[MX][26]{};
int pass[MX]{};
string End[MX]{};
int cnt;

class Solution {
private:
    void buildTrie(vector<string>& words) {
        cnt = 1;
        for(string s : words) {
            // 插入新的節點
            int cur = 1;
            pass[cur]++;
            for(char ch : s) {
                int path = ch - 'a';
                if(trie[cur][path] == 0) {
                    trie[cur][path] = ++cnt;
                }
                cur = trie[cur][path];
                pass[cur]++;
            }
            End[cur] = s; // 結尾紀錄字串，在查找時如果走訪到這裡，代表收集到了這個單字。
        }
    }

    void clearTrie() {
        for (int i = 1; i <= cnt; i++) {
            memset(trie[i], 0, sizeof(trie[i]));
            pass[i] = 0;
            End[i].clear();
        }
    }

    // i, j: 此時來到的位置, cur: 當前所在的節點編號
    // return 收集到的字串有多少個，用於剪枝。
    int dfs(vector<vector<char>>& board, int i, int j, int cur, vector<string>& res) {
        if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] == 0) {
            return 0;
        }

        // 剪枝
        // cur = 0: 沒有路存在
        // pass[cur] = 0: 下面的節點都已經被收集完畢
        // 不寫 cur = 0 || pass[cur] = 0 可以簡化，因為路不存在的話，pass[cur] 肯定是 0 
        int path = board[i][j] - 'a';
        cur = trie[cur][path];
        if(pass[cur] == 0) { 
            return 0;
        }
        
        char temp = board[i][j]; // 用於還原現場
        int collected = 0; // 從當前位置出發，一共可以收集到多少字串
        if(!End[cur].empty()) { // 當前位置是某字串的終點
            collected++;
            res.push_back(End[cur]);
            End[cur].clear(); // 清空
        }

        board[i][j] = 0; // 標註為走訪過
        collected += dfs(board, i + 1, j, cur, res);
        collected += dfs(board, i - 1, j, cur, res);
        collected += dfs(board, i, j + 1, cur, res);
        collected += dfs(board, i, j - 1, cur, res);
        pass[cur] -= collected;
        board[i][j] = temp; // 還原現場

        return collected;
    }

public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        int n = board.size(), m = board[0].size();
        buildTrie(words);
        vector<string> res;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                dfs(board, i, j, 1, res); // 從根結點開始搜索，board 的每一個格子都可以做為起點
            }
        }
        clearTrie();
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(K\times{L}+M\times{N}\times3^L)$

  • 將所有單字插入字典樹，需要 $O(K\times{L})$的時間
  • dfs搜索，每次有四個方向走，最深會走到 $L$ 層，接下來每一步不能回頭，最多只會有三個方向，因此單次dfs的時間上限為$O(3^L)$

• 空間複雜度：$O(K\times{L})$

  • Trie 占用的空間：最糟情況是 $O(K\times{L})$
  • 遞迴呼叫堆疊：dfs 的最大深度咀嚼於單字的最大長度，因此棧空間為 $O(L)$。
  • 兩者取最大值，整體空間由 Trie 主導，為 $O(K\times{L})$