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;}
};