212. Word Search II.md

212. Word Search II

思路

这题是79. Word Search的升级版，79题是判断某个单词是否存在与board中，而此题是给了一堆单词，让返回所有存在的单词。

亲测按照79那样直接搜索是会超时的（不然就不是hard题了），那我们只好考虑更加高效的方法。由于是在一个单词集合中查询，那么我们考虑用字典树（Trie），所以我们可以直接把208题的字典树实现拿过来用，不过只用到了insert操作。

字典树建好后，我们就可以DFS了，一旦遇到了字典树某个节点is_last_letter == true就说明找到了，将此时对应的单词加入结果数组中；为了避免下一次DFS时重复找到这个单词，我们应该将这里的is_last_letter设为false，表示单词集里面没有这个单词了。

代码中使用了一个小技巧，类似79题思路二那样，我们使用DFS时不另开visited数组，而是用原数组board来记录某个元素是否被访问过，若被访问过就将board对应位置改成字符*，注意DFS结束前要改回来。

C++

struct TrieNode{
    bool is_last_letter;    // 是否是某个单词的结尾
    char letter;
    vector<TrieNode *>next; // 孩子们
    TrieNode(char cc): is_last_letter(false), letter(cc),
                       next(vector<TrieNode *>(26, NULL)){}
};

class Trie {
private:
    TrieNode *root;
public:
    Trie() {
        root = new TrieNode('\0'); // 根节点不包含字符
        root -> is_last_letter = true;
    }
    
    TrieNode* getRoot(){return root;}
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        if(word.empty()) return;
        TrieNode *p = root;
        for(int i = 0; i < word.size(); i++){
            int idx = word[i] - 'a';
            if(NULL == (p -> next)[idx]) // 没找到, 插入即可
                (p -> next)[idx] = new TrieNode(word[i]);
            p = (p -> next)[idx];
        }
        p -> is_last_letter = true;
    }
};

class Solution {
private:
    int row, col;
    vector<string>res;
    const vector<int>dx = {0,0,1,-1}, dy = {1,-1,0,0};
    void DFS(vector<vector<char>>& board,
             vector<TrieNode *>&nodes, int i, int j, string word){
        if(i < 0 || i >= row || j < 0 || j >= col || board[i][j] == '*') return;
        
        TrieNode *node = nodes[board[i][j] - 'a'];
        if(!node) return;
        
        word.append(1, board[i][j]);
        char tmp = board[i][j]; board[i][j] = '*';
        if(node -> is_last_letter) {
            res.push_back(word);
            // 避免下一次DFS时重复找到这个单词
            node -> is_last_letter = false;
        }
        for(int k = 0; k < 4; k++)
            DFS(board, node -> next, i+dx[k], j+dy[k], word);

        board[i][j] = tmp;
    }
    
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        row = board.size();
        if(!row || words.empty()) return res;
        col = board[0].size();
        
        Trie tree;
        for(string word: words) tree.insert(word); 
        
        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++)
                DFS(board, tree.getRoot() -> next, i, j, "");
        
        return res;
    }
};