leetcode 212. 单词搜索 II

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

这里我们需要在字符表中查找words中的单词,如果我们暴力搜索，然后再去检验的化，效率很低，并且每个点都需要搜索所以行不通
这里我们直接建立words的Trie 然后dfs 建立的Trie 大大减少了dfs的范围

Trie节点Trienode 

这里使用map<char,Tirenode*>内存确实效率更好

struct Tirenode
{
   unordered_map<char,Tirenode*> next;
   string s="";                       //标记单词 
};

 Trie节点的添加

 void insert_(string& word)
 {                
     auto node=this->root;     //遍历节点
     for(auto c:word)
     {
         if(!node->next.count(c)) node->next[c]=new Tirenode();  
         node=node->next[c];
     }
     node->s=word; //标记单词
 }

dfs查找

 我们已经将words的单词假如到了Trie结构中
 所以我们只要dfs board中的字符看是否能搜索到temp不为空字符的情况即可
 去重的话如果我们搜索到了单词temp则将它置空，表示我们已经push_back过了 

 void dfs(point p,vector<vector<char>>& board,Tirenode* temp)
    {
        auto [x,y]=p;        //结构化绑定
        char c=board[x][y];  //记录当前字母
        if(!temp->next.count(c)) return;  //搜索到尾了 则退出递归
        
        //搜索到单词
        if(temp->next[c]->s!="") {dp.push_back(temp->next[c]->s);temp->next[c]->s="";};        

        //标记当前单词表示已经搜索
        board[x][y]='#';
        
        //dfs搜索
        for(int i=0;i<4;i++)
        {
            int nx=x+a[i];
            int ny=y+b[i];
            if(nx>=0&&nx<board.size()&&ny>=0&&ny<board[0].size()&&board[nx][ny]!='#')
            {
                dfs({nx,ny},board,temp->next[c]);
            }
        }
        
        //回溯
        board[x][y]=c;
    }

完整代码： 

class Solution {
public:
    typedef pair<int,int> point;
    vector<string> dp;
    int a[4]={0,0,1,-1};
    int b[4]={1,-1,0,0};
    int max_=0;
    struct Tirenode
    {
        unordered_map<char,Tirenode*> next;
        string s="";
    };
    Tirenode* root=new Tirenode();
    void insert_(string& word)
    {
        auto node=this->root;
        for(auto c:word)
        {
            if(!node->next.count(c)) node->next[c]=new Tirenode();
            node=node->next[c];
        }
        node->s=word;
    }
    void dfs(point p,vector<vector<char>>& board,Tirenode* temp)
    {
        auto [x,y]=p;
        char c=board[x][y];
        if(!temp->next.count(c)) return;
        if(temp->next[c]->s!="") {dp.push_back(temp->next[c]->s);temp->next[c]->s="";};
        board[x][y]='#';
        for(int i=0;i<4;i++)
        {
            int nx=x+a[i];
            int ny=y+b[i];
            if(nx>=0&&nx<board.size()&&ny>=0&&ny<board[0].size()&&board[nx][ny]!='#')
            {
                dfs({nx,ny},board,temp->next[c]);
            }
        }
        board[x][y]=c;
    }
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        for(auto s:words)  insert_(s);  
        int m=board.size();
        int n=board[0].size();
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                dfs({i,j},board,this->root);
            }
        }
        return dp;
    }
};