题目
给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。
单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例 1：
输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"] 输出：["eat","oath"]
示例 2：
输入：board = [["a","b"],["c","d"]], words = ["abcb"] 输出：[]
解题
方法一：每个单词分别dfs(超时)
在题目leetcode-79：单词搜索里面，直接dfs不会超时，效果和字典树差不多，但是遇到多次查询的时候，直接回溯的效果，远不如字典树
class Solution { public: int m,n; vector<vector<int>> dirs={{-1,0},{0,-1},{1,0},{0,1}}; bool dfs(vector<vector<char>>& board,string& word,vector<vector<bool>>& visited,int index,int x,int y){ if(index==word.size()) return true; if(x<0||x>=m||y<0||y>=n||visited[x][y]) return false; if(word[index]!=board[x][y]) return false; visited[x][y]=true; for(vector<int>& dir:dirs){ int nx=x+dir[0],ny=y+dir[1]; if(dfs(board,word,visited,index+1,nx,ny)) return true; } visited[x][y]=false; return false; } vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { m=board.size(),n=board[0].size(); vector<string> res; for(string& word:words){ bool flag=false; vector<vector<bool>> visited(m,vector<bool>(n,false)); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(dfs(board,word,visited,0,i,j)){ flag=true; break; } } if(flag) break; } if(flag) res.push_back(word); } return res; } };
方法二：字典树+dfs回溯
思路：
1.先将要查询的单词全部插入到字典树中
2.从board的每个元素开始遍历，找到在字典树中出现的单词，直接加入到res中
class Trie{ public: bool isEnd; vector<Trie*> next; string str; Trie(){ isEnd=false; next=vector<Trie*>(26,nullptr); } void insert(string& word){ Trie* node=this; for(char c:word){ if(node->next[c-'a']==nullptr) node->next[c-'a']=new Trie(); node=node->next[c-'a']; } node->isEnd=true; node->str=word;//结尾直接记录单词(目的是为了遍历到End，将单词直接插入到res中) } }; class Solution { public: Trie* trie; int m,n; vector<string> res; vector<vector<int>> dirs={{-1,0},{0,-1},{1,0},{0,1}}; vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { trie=new Trie(); m=board.size(),n=board[0].size(); for(string& word:words){ trie->insert(word); } vector<vector<bool>> visited(m,vector<bool>(n,false)); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ Trie* node=trie->next[board[i][j]-'a']; if(node!=nullptr){ visited[i][j]=true; dfs(board,i,j,node,visited); visited[i][j]=false; } } } return res; } void dfs(vector<vector<char>>& board,int x,int y,Trie* node,vector<vector<bool>>& visited){ if(node->str!=""){ res.push_back(node->str); node->str=""; } for(vector<int>& dir:dirs){ int nx=x+dir[0],ny=y+dir[1]; if(nx<0||nx>=m||ny<0||ny>=n||visited[nx][ny]) continue; char c=board[nx][ny]; if(node->next[c-'a']==nullptr) continue; visited[nx][ny]=true; dfs(board,nx,ny,node->next[c-'a'],visited); visited[nx][ny]=false; } } };
优化一：字典树(带删除功能)+dfs回溯
使用带删除功能的字典树，可以避免多次无效遍历
对每个节点增加一个count引用计数的属性
删除字符串时候，对应引用计数-1
class Trie{ public: bool isEnd; vector<Trie*> next; int count;//引用计数 string str; Trie(){ isEnd=false; count=0;//引用计数初始化 next=vector<Trie*>(26,nullptr); } void insert(string& word){ Trie* node=this; for(char c:word){ if(node->next[c-'a']==nullptr){ node->next[c-'a']=new Trie(); } node=node->next[c-'a']; node->count++;//对应节点引用计数+1 } node->isEnd=true; node->str=word; } void del(string& word){ Trie* node=this; for(char c:word){ Trie* tmp=node->next[c-'a']; tmp->count--;//对应节点引用计数-1 node=tmp; } } }; class Solution { public: Trie* trie; int m,n; vector<string> res; vector<vector<int>> dirs={{-1,0},{0,-1},{1,0},{0,1}}; vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { trie=new Trie(); m=board.size(),n=board[0].size(); for(string& word:words){ trie->insert(word); } vector<vector<bool>> visited(m,vector<bool>(n,false)); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ Trie* node=trie->next[board[i][j]-'a']; if(node!=nullptr&&node->count>0){//不空，并且没有被删除 visited[i][j]=true; dfs(board,i,j,node,visited); visited[i][j]=false; } } } return res; } void dfs(vector<vector<char>>& board,int x,int y,Trie* node,vector<vector<bool>>& visited){ if(node->str!=""){ res.push_back(node->str); trie->del(node->str); node->str=""; } for(vector<int>& dir:dirs){ int nx=x+dir[0],ny=y+dir[1]; if(nx<0||nx>=m||ny<0||ny>=n||visited[nx][ny]) continue; char c=board[nx][ny]; if(node->next[c-'a']==nullptr||node->next[c-'a']->count==0) continue;//不空，并且没有被删除 visited[nx][ny]=true; dfs(board,nx,ny,node->next[c-'a'],visited); visited[nx][ny]=false; } } };
在引入带删除功能的字典树后，查找性能大幅提升，但是内存泄漏还没有去解决。
