题目

题目连接
设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。

实现 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;
    }
};