132. Word Search II

Code(Language:C++) (Judger:ip-172-31-21-252)

class trieNode{
public:     
    trieNode *child[26]; 
    string word;
    trieNode(){
        for(int i = 0; i < 26; i++){
            child[i] = NULL; 
        }
        word = ""; 
    }
}; 

class trieTree{
public: 
    trieNode *root; 
    trieTree(){
        root = new trieNode(); 
    }
    void insert(string word){
        trieNode *copy = root; 
        int size = word.size();
        if(size == 0){
            return; 
        }
        for(int i = 0; i < size; i++){
            int idx = word[i] - 'a';
            if(copy->child[idx] == NULL){
                copy->child[idx] = new trieNode(); 
            }
            copy = copy->child[idx]; 
        }
        copy->word = word; 
        return; 
    }
}; 
class Solution {
public:
    /**
     * @param board: A list of lists of character
     * @param words: A list of string
     * @return: A list of string
     */
    const vector<int> dx = {0, 0, -1, 1};
    const vector<int> dy = {-1, 1, 0, 0};
    const int dir = 4; 
    vector<string> wordSearchII(vector<vector<char>> &board, vector<string> &words) {
        // write your code here
        // if search each word one by one, it is same as word search I. 
        // word search I complexity is m * n * （4 ^ wordLength）
        // to optimize, need to use the trie. 
        // 1, declare trie node class。
        // 2, declare trieTree class。
        // 3, define trieTree and insert the words in the tree.
        // 4, dfs with the trieTree as input
        vector<string> res; 
        const int size = words.size();
        if(size == 0){
            return res; 
        }
        trieTree *tree = new trieTree(); 
        
        for(int i = 0; i < size; i++){
            tree->insert(words[i]); 
        }
        const int m = board.size();
        if(m == 0){
            return res; 
        }
        const int n = board[0].size();
        vector<vector<int>> visited(m, vector<int>(n, 0)); //注意放在外面，能提高很多的计算速度 
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                
                if(tree->root->child[board[i][j] - 'a'] - 'a'){
                    dfs(board, i, j, visited, tree->root, res); 
                }
            }
        }
        return res; 
    }
    void dfs(vector<vector<char>> &board, int x, int y, vector<vector<int>> &visited, trieNode *node, vector<string> &res){
        if(node->word != ""){
            res.push_back(node->word);
            node->word = "";
            return; 
        }
        if(x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || visited[x][y]){
            return; 
        }
        if(node->child[board[x][y] - 'a'] == NULL){
            return; 
        }
        visited[x][y] = 1; 
        for(int i = 0; i < dir; i++){
            dfs(board, x + dx[i], y + dy[i], visited, node->child[board[x][y] - 'a'], res); 
        }
        visited[x][y] = 0; 
        return; 
    }
};