745. 前缀和后缀搜索
设计一个包含一些单词的特殊词典并能够通过前缀和后缀来检索单词。
实现 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” 。
提示
1 < words.length < 104 1 < words[i].length < 7 1 < pref.length,suff.length < 7 words[i]、pref 和 suff 仅由小写英文字母组成 最多对函数 f 执行 1e4 次调用
解析
- 查询是否存在该前缀单词可以使用前缀字典树查找
- 查询后缀是否存在可以将单词反转之后插入字典树查询时将后缀发转查询即可例如[[[“abbc”]],[“ab”,“bc”]]将abbc插入前缀树将abbc反转为cbba查cb即可。
- 另外插入时字典树每个节点中还应该存入单词下标说明下标单词可以产生正在查询的前缀
- 在前缀字典树中查询pref获取该前缀的单词下标在后缀字典树中查询suff单词下标两者交集即是结果返回最大值即可
- 为什么需要建立两个字典树如果建立一个字典树[[[“abbc”]],[“a”,“a”]]将"abbc"插入“cbba” 插入pref查询到结果为0suff查询结果也为0明显错误
- 需要注意的是我们在插入的时候将单词按顺序插入字典树因此每个节点中的单词下标应该是升序排列在我们求交集最大值时可以利用这一性质降低复杂度
- 真实的测试用例比提示中大。
代码
class WordFilter {struct Node{Node* son[26];vector idx;bool isEndfalse;};public:void insert(Node* root,stringroot;for(auto a : s){int ca-a;if(!cur->son[c])cur->son[c]new Node();curcur->son[c];// 下标id的单词经过该字母cur->idx.push_back(id);}cur->isEndtrue;}void insert1(Node* root,stringroot;for(int is.size()-1;i>0;i--){int cs[i]-a;if(!cur->son[c])cur->son[c]new Node();curcur->son[c];// 下标id的单词经过该字母cur->idx.push_back(id);}cur->isEndtrue;}int searchPre(Node* root,Node* root1,string-1;Node* cur1root;for(int i0;ison[c]){return -1;break;}cur1cur1->son[c];}Node* curroot1;// 需要查suff的发转字符串对比后缀for(int isuff.size()-1;i>0;i--){int csuff[i]-a;if(!cur->son[c]){return -1;break;}curcur->son[c];}// 不用引用过不了// l1指向pref最后一个字母对应单词数组vector cur1->idx;// l2指向suff最后一个字母对应单词数组vector cur->idx;int n l1.size(), m l2.size();// l1,l2都是从小到大顺序插入从大到小遍历找最大值for(int i n - 1, j m - 1; i > 0 0; ) {if(l1[i] > l2[j]) i--;else if(l1[i] < l2[j]) j--;else return l1[i];}return -1;}Node* root;Node* root1;WordFilter(vectornew Node();root1new Node();// 将单词同时插入前缀后缀字典树for(int i0;i