题目
设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。
实现 WordFilter 类：
- WordFilter(string[] words) 使用词典中的单词 words 初始化对象。
- f(string pref, string suff) 返回词典中具有前缀 prefix 和后缀 suff 的单词的下标。如果存在不止一个满足要求的下标，返回其中 最大的下标 。如果不存在这样的单词，返回 -1 。
示例：
输入 ["WordFilter", "f"] [[["apple"]], ["a", "e"]] 输出 [null, 0] 解释 WordFilter wordFilter = new WordFilter(["apple"]); wordFilter.f("a", "e"); // 返回 0 ，因为下标为 0 的单词：前缀 prefix = "a" 且 后缀 suff = "e" 。
解题
方法一：双字典树
前缀插入其中一个字典树
后缀插入另一个字典树
字典树的每个节点，保存索引
最后根据前缀和后缀获得公共的最大索引
本题双字典树一不小心就会出现超时的问题
写法一：双字典树（超时写法）
使用set去获得最大公共索引，17个样例只通过4个，使用vector，17个样例通过14个。
class Trie{ public: vector<int> index; vector<Trie*> next=vector<Trie*>(26,nullptr); void insert(string& word,int index){ 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->index.push_back(index); } } vector<int> search(string& word){ Trie* node=this; for(char c:word){ if(node->next[c-'a']){ node=node->next[c-'a']; }else return {}; } return node->index; } }; class WordFilter { public: Trie* prefixTrie; Trie* suffixTrie; WordFilter(vector<string>& words) { prefixTrie=new Trie(); suffixTrie=new Trie(); for(int i=0;i<words.size();i++){ string word=words[i]; prefixTrie->insert(word,i); reverse(word.begin(),word.end()); suffixTrie->insert(word,i); } } int f(string pref, string suff) { vector<int> l1=prefixTrie->search(pref); reverse(suff.begin(),suff.end()); vector<int> l2=suffixTrie->search(suff); int m=l1.size(),n=l2.size(); for(int i=m-1,j=n-1;i>=0&&j>=0;){ if(l1[i]>l2[j]) i--; else if(l1[i]<l2[j]) j--; else return l1[i]; } return -1; } };
写法二：字典树（通过）
最后设置了引用，返回，通过了。
原因是查找字典树，返回vector进行了大量拷贝。使用引用返回，可以大幅提升速度。
可以设置一个全局的空vector，用于引用返回，因为局部变量是没法引用返回的。
class Trie{ public: vector<int> index; vector<Trie*> next=vector<Trie*>(26,nullptr); vector<int> emptyVec;//设置了空vector void insert(string& word,int index){ 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->index.push_back(index); } } vector<int>& search(string& word){//返回值引用 Trie* node=this; for(char c:word){ if(node->next[c-'a']){ node=node->next[c-'a']; }else return emptyVec;//全局的空vec可以引用返回 } return node->index; } }; class WordFilter { public: Trie* prefixTrie; Trie* suffixTrie; WordFilter(vector<string>& words) { prefixTrie=new Trie(); suffixTrie=new Trie(); for(int i=0;i<words.size();i++){ string word=words[i]; prefixTrie->insert(word,i); reverse(word.begin(),word.end()); suffixTrie->insert(word,i); } } int f(string pref, string suff) { vector<int>& l1=prefixTrie->search(pref);//引用 reverse(suff.begin(),suff.end()); vector<int>& l2=suffixTrie->search(suff);//引用 int m=l1.size(),n=l2.size(); for(int i=m-1,j=n-1;i>=0&&j>=0;){ if(l1[i]>l2[j]) i--; else if(l1[i]<l2[j]) j--; else return l1[i]; } return -1; } };
方法二：哈希
预先计算出每个单词的前缀后缀组合可能性，用特殊符号连接，作为键，对应的最大下标作为值保存入哈希表。检索时，同样用特殊符号连接前后缀，在哈希表中进行搜索。
如果将每个前缀和后缀都保存到哈希表，作为二级哈希，会超时。
通过特殊字符，将它们绑定到一起，只要做一级哈希。
class WordFilter { public: unordered_map<string,int> map; WordFilter(vector<string>& words) { for(int i=0;i<words.size();i++){ string word=words[i]; int m=word.size(); for(int prefixLen=1;prefixLen<=m;prefixLen++){ for(int suffixLen=1;suffixLen<=m;suffixLen++){ string key=word.substr(0,prefixLen)+"#"+word.substr(m-suffixLen,suffixLen); map[key]=i; } } } } int f(string pref, string suff) { string key=pref+"#"+suff; return map.count(key)?map[key]:-1; } };
