前缀树]leetcode474:连接词(hard)"/>
[前缀树]leetcode474:连接词(hard)
题目:
题解:
主要利用前缀树解题,先建树,然后进行搜索操作。
这里简单讲解一下搜索单词,例如寻找catsdogcats,当i为2时,我们在前缀树发现cat是一个子单词,然后开始search(sdogcats),然而发现这个并不是子单词,那就证明以cat作为分界词就错了。我们继续for循环,然后匹配到cats时,在递归匹配dogcats
,直到for循环结束!
代码如下:
class Trie{
private:bool is_string;Trie *next[26];
public:Trie(){is_string=false;memset(next,0,sizeof(next));}void insert(string word){Trie *root=this;for(const auto& w:word){if(root->next[w-'a']==nullptr)root->next[w-'a']=new Trie();root=root->next[w-'a'];}root->is_string=true;}bool search(string word,int index,int count){Trie *root=this;//每次从根节点开始搜索for(int i=index;i<word.size();++i){if(root->next[word[i]-'a']==nullptr)return false;//word的某个字符不在前缀树中root=root->next[word[i]-'a'];if(root->is_string){//到达某个单词尾if(i==word.size()-1)return count>=1;//count的数量至少为2个,若遍历到最后只有一个单词,则count的值还是为0//已前count位的单词作为分解词继续匹配下一个单词,下个单词满足count才能返回ture,否则继续寻找下一个分界单词if(search(word,i+1,count+1))return true;}}return false;}
};
class Solution {
public:vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {Trie *root=new Trie();for(const auto &word:words){root->insert(word);}vector<string> result;for(const auto &word:words){if(root->search(word,0,0))result.push_back(word);}return result;}
};
更多推荐
[前缀树]leetcode474:连接词(hard)
发布评论