前缀树]leetcode212:单词搜索 Ⅱ(hard)"/>
[前缀树]leetcode212:单词搜索 Ⅱ(hard)
题目:
题解:前缀树+DFS
- 1)关于前缀树的实现,可参考:这里。
- 2)DFS深度搜索二维数组,设置好递归边界+递归式子,每个点向四周进行DFS,存在于前缀树中的字符标记为’#’,在DFS完成之后还原成以前的字符即可。
代码如下:
class Trie{
private:bool is_string;Trie *next[26];string str;
public:Trie(){is_string=false;str="";memset(next,0,sizeof(next));}void insert(string word)//插入单词,建立前缀树{Trie *root=this;for(auto w:word){if(root->next[w-'a']==nullptr)root->next[w-'a']=new Trie();root=root->next[w-'a'];}root->is_string=true;root->str=word;}void search(vector<string>& result,vector<vector<char>>& board){Trie *root=this;for(int i=0;i<board.size();++i)//每一个坐标都要开始dfsfor(int j=0;j<board[0].size();++j)helper(result,board,root,i,j);}void helper(vector<string>& result,vector<vector<char>>& board,Trie* note,int x,int y){if(note->is_string==true){//在board中找到words中一个单词,添加到result中note->is_string=false;//将该单词标记为false,防止在word中再次递归到这个单词,从而造成重复添加result.push_back(note->str);return;}if(x<0||x==board.size()||y<0||y==board[x].size())return;//超出边界,不能继续递归if(board[x][y]=='#'||note->next[board[x][y]-'a']==nullptr)return;//坐标(x,y)对应的字符不在前缀树中,递归方向不对,返回到上一个坐标note=note->next[board[x][y]-'a'];//note指向下一个字符节点char temp=board[x][y];board[x][y]='#';//标记(x,y)对应的字符已被访问过,防止同一个单元格内的字符在一个单词中重复使用helper(result,board,note,x+1,y);helper(result,board,note,x-1,y);helper(result,board,note,x,y+1);helper(result,board,note,x,y-1);board[x][y]=temp;}
};
class Solution {
public:vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {Trie *root=new Trie();vector<string> result;for(auto word:words)root->insert(word);root->search(result,board);return result;}
};
更多推荐
[前缀树]leetcode212:单词搜索 Ⅱ(hard)
发布评论