212. 单词搜索 II/++

class Solution {
    struct Node{
        char c;
        bool finished;
        string word;
        Node* children[26];
        Node(char ch) :c(ch), finished(false) { 
			memset(children, 0, sizeof(children));
		}
    };
    Node* trie = new Node(0);
    vector<vector<int>> direction{{1,0},{-1,0},{0,1},{0,-1}};
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> res;
        if(board.empty()) return res;
        int m = board.size();
        int n = board[0].size();
        vector<vector<bool>> visited(m,vector<bool>(n,false));
        
        buildTrie(words);
        
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                dfs(board,visited,m,n,i,j,trie->children[board[i][j]-'a'],res);
            }
        }
        return res;
    }
    void dfs(const vector<vector<char>>& board, vector<vector<bool>>& visited, 
    		int m, int n, int x,int y, Node* node, vector<string>& res){
        if(x<0 || x>=m || y<0 || y>=n) return;
        if(visited[x][y]) return;
        if(!node || node->c != board[x][y]) return;
        
        if(!node->word.empty() && !node->finished){
            res.push_back(node->word);
            node->finished = true;
        }
        
        visited[x][y] = true;
        
        for(int i=0;i<26;++i){
            if(!node->children[i]) continue;
            for(int j=0;j<4;++j){
               dfs(board,visited,m,n,x+direction[j][0],y+direction[j][1],node->children[i],res);
            }
        }
        
        visited[x][y]=false;
    }
    
    
    void buildTrie(const vector<string>& words){
        for(auto& word:words){
            insert(word);
        }
    }
    void insert(const string& word){
        Node* t = trie;
        for(auto c:word){
            if(!t->children[c-'a']){
                t->children[c-'a'] = new Node(c);
            }
            t = t->children[c-'a'];
        }
        t->word = word;
    }
};