Trie树+爆搜

class Trie{
    public:
    struct Node{
        bool eow;
        Node* nc[26];
        Node(){eow = false; for (int i=0;i<26;i++) nc[i] = NULL;}
    };
    Node* root = new Node();
    Trie(){root->eow = true;}
    void insert(string s){
        Node* tmp = root;
        for (auto c:s){
            int idx = c-'a';
            if (tmp->nc[idx]) tmp = tmp->nc[idx];
            else {
                tmp->nc[idx] = new Node();
                tmp = tmp->nc[idx];
            }
        }
        tmp->eow = true;
    }
};
unordered_set<string> ans;

int dx[4] ={-1,0,1,0}, dy[4] ={0,-1,0,1};
int m,n;
vector<vector<bool>> st;
string path;
void dfs(vector<vector<char>>& board, int x, int y,Trie::Node* p){

    if (p->eow) {ans.insert(path);}
    st[x][y] = true;
    for (int i = 0;i<4;i++){
        int xx=x+dx[i], yy = y+dy[i];

        if (xx>=0 &&xx<m && yy>=0 && yy<n &&!st[xx][yy]&&p->nc[board[xx][yy]-'a']!=NULL){

            // st[xx][yy] = true;
            path+=board[xx][yy];
            // cout<<path<<endl;
            dfs(board,xx,yy,p->nc[board[xx][yy]-'a']);
            // st[xx][yy] = false;
            path.pop_back();
        }
    }
    st[x][y] = false;
}

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        Trie t;
        ans = unordered_set<string>();
        m = board.size(), n = board[0].size();

        st = vector<vector<bool>>(m, vector<bool>(n,0));

        for (auto w:words){
            t.insert(w);
        }
        for (int i = 0;i<m;i++){
            for (int j =0;j<n;j++){
                int idx = board[i][j] - 'a';
                if (t.root->nc[idx]) {path += board[i][j]; dfs(board, i, j, t.root->nc[idx]);path.pop_back();}

            }
        }
        // Node* p = t.root->nc['e'-'a'];
        return vector<string> (ans.begin(),ans.end());
    }
};