[前缀树]leetcode745：前缀和后缀搜索(hard)

前缀树]leetcode745：前缀和后缀搜索(hard)"/>

[前缀树]leetcode745：前缀和后缀搜索(hard)

题目：

题解：

构造两个字典树，一个正序查前缀，一个逆序查后缀，并且节点记录访达权值，查找的时候排除边缘条件后对比权值就行。

代码如下：

class Trie{
private:vector<int> subs;Trie* next[26];
public:Trie(){memset(next,0,sizeof(next));}//插入单词void insert(string& word,int i){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->subs.push_back(i);}}vector<int>* startsWith(string& prefix){Trie* root=this;for(const auto& p:prefix){if(root->next[p-'a']==nullptr)return nullptr;root=root->next[p-'a'];}return &root->subs;}
};
class WordFilter {
private:Trie* pre;//建立前缀树Trie* suf;//建立后缀树int size=0;
public:WordFilter(vector<string>& words) {pre=new Trie();suf=new Trie();for(int i=0;i<words.size();++i){pre->insert(words[i],i);string temp=words[i];//正向插入单词到前缀树reverse(temp.begin(),temp.end());suf->insert(temp,i);//反向插入单词到后缀树}int size=words.size()-1;}int f(string prefix, string suffix) {//前缀字符串和后缀字符串都为空，最大权重就是words的大小了if(prefix.empty()&&suffix.empty())return size;vector<int>* v1=pre->startsWith(prefix);reverse(suffix.begin(),suffix.end());vector<int>* v2=suf->startsWith(suffix);f(v1==nullptr||v2==nullptr)return -1;//前缀或后缀有一个为空，就表示没有这样的单词if(prefix.size()==0)return *(v2->end()-1);//前缀字符串为空，返回后缀字典树中的最大权重if(suffix.size()==0)return *(v1->end()-1);//后缀字符串为空，返回前缀字典树中的最大权重auto it1=v1->end()-1;auto it2=v2->end()-1;while(it1>=v1->begin()&&it2>=v2->begin())//查找的时候排除边缘条件后对比权值就行{if(*it1==*it2)return *it1;if(*it1>*it2)it1--;else it2--;}return -1;}
};