字典树+回溯

• 暴力做法是，对board进行DFS,得到所有路径上可能的单词并看是否在words中。此法时间复杂度过大会超时
• 剪枝：将Words中字符串插入字典树中，这样搜所网格时，当前搜索路径构成的前缀字符串在Trie树出现时，才继续往下搜索，否则回溯。因为该前缀串在Trie中未出现，往下搜索的单词必然不在words中。
• 防止搜索网格时，已经访问过的字符被重复访问：引入visite数组

• 防止重复字符串添加到结果数组：搜索到一个单词后，将其所在结点的is_end置为false;

• 本题采用智能指针实现结点的内存管理

class Solution {
    struct TrieNode{
        bool is_end;
        string str;                                    //存储以该结点为结尾的单词
        vector<shared_ptr<TrieNode>> son;
        TrieNode():is_end(false),str(""),son(26,nullptr){}
    };
    struct Trie{
        shared_ptr<TrieNode> root;

        Trie(){
            root=make_shared<TrieNode>();
        }

        void insert(const string &word){
            auto p=root;
            for(const auto &c:word){
                int u=c-'a';
                if(!p->son[u]) p->son[u]=make_shared<TrieNode>();
                p=p->son[u];
            }
            p->is_end=true;
            p->str=word;                                //最后一个结点保存该单词
        }
    };

    int row,col;
    vector<vector<bool>> visited;
    vector<string> res;
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        if(board.empty() || words.empty()) return res;

        row=board.size();
        if(row) col=board[0].size();
        visited=vector<vector<bool>>(row,vector<bool>(col,false));

        auto tree=make_shared<Trie>();              //建树
        auto root=tree->root;                       //访问根节点

        for(const auto &str:words){
            tree->insert(str);
        }
        for(int i=0;i<row;++i){
            for(int j=0;j<col;++j){
                int u=board[i][j]-'a';
                dfs(board,i,j,root->son[u]);
            }
        }
        return res;
    }

    void dfs(vector<vector<char>>& board,int x,int y,shared_ptr<TrieNode> root){
        if(!root) return;                           //剪枝，trie树中不存在当前前缀字符串时，剪枝回溯
        if(root->is_end){                           
            res.push_back(root->str);
            root->is_end=false;                     //搜索到一个单词后，删除该节点的标记，防止重复添加结果
        }                                           //此时并不能回溯，因为沿该单词链可能还会有其他单词

        visited[x][y]=true;                         //保存现场
        int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
        for(int d=0;d<4;++d){
            int a = x + dx[d], b = y + dy[d];
            if(a>=0 && a<row && b>=0 && b<col && !visited[a][b]){
                int u=board[a][b]-'a';
                dfs(board,a,b,root->son[u]);
            }
        }
        visited[x][y]=false;                        //恢复现场
    }
};