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

题目：

题解：

思路1：统计每个单词的所有前缀与后缀组合起来的单词，然后存在 hashmap 中，进行暴力匹配就行。

---

思路2：前缀树

• 以后再补吧，现在没时间。。。

题解：

class WordFilter {
public:
    unordered_map dict;
    // 将每个单词所有前缀与后缀的组合进行枚举，用特殊符号#来连接前缀与后缀。对于相同的前缀与后缀只有保留最大的下标即可
    WordFilter(vector& words) {
        for(int i=0,n=words.size();i
            int m=words[i].size();
            // 前缀与后缀的组合
            for(int j=1;j<=m;j++)
                for(int k=1;k<=m;++k){
                    string word=words[i].substr(0,j)+"#"+words[i].substr(m-k);
                    dict[word]=i;
                }
        }
    }
    
    int f(string pref, string suff) {
        string word=pref+"#"+suff;
        return dict.count(word)?dict[word]:-1;
    }
};