题目描述

Given many words, words[i] has weight i.

Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix). It will return the word with given prefix and suffix with maximum weight. If no word exists, return -1.

Examples:

Input:
WordFilter(["apple"])
WordFilter.f("a", "e") // returns 0
WordFilter.f("b", "") // returns -1

Note:

1. words has length in range [1, 15000].
2. For each test case, up to words.length queries WordFilter.f may be made.
3. words[i] has length in range [1, 10].
4. prefix, suffix have lengths in range [0, 10].
5. words[i] and prefix, suffix queries consist of lowercase letters only.

题意：给定多个 words，words[i] 的权重为 i 。

设计一个类 WordFilter 实现函数WordFilter.f(String prefix, String suffix)。这个函数将返回具有前缀 prefix 和后缀suffix 的词的最大权重。如果没有这样的词，返回 -1。

算法1

(Trie)

题解：朴素想法就是分别建立前缀树和后缀树，然后用DFS求解前缀集合和后缀集合。求两个集合的交集。我们对每个单词的所有后缀包括空串以及自己，拼接上#,在拼接上原单词.把整个字符串插入到Trie中，以apple为例,我们会插入 #apple, e#apple, le#apple, ple#apple, pple#apple, apple#apple 到Trie树中. 如果查询前缀是 ap,后缀是le的单词,我们可以够着这样的查询语句 le#ap。插入的时候，路径上每个节点都更新为当前的单词的权值。

时间复杂度：每个长度为$L$单词我们插入了$L + 1$个单词，总共$N$个单词，那么插入的时间复杂度为$O(N\*L^2)$，对于每次查询的时间复杂度为$O(L)$，总共$Q$次查询，那么总的时间复杂度为$O(N*L^2 + QL)$。

C++ 代码

class WordFilter {
public:
    int son[1500000][27] = {},val[1500000] = {},idx = 0;
    void insert(string &s,int id)
    {
        int p = 0,u;
        for(auto c : s)
        {
            if(c == '#') u = 26;
            else u = c -'a';
            if(!son[p][u]) son[p][u] = ++idx;
            p = son[p][u];
            val[p] = id;
        }
    }
    int query(string &s)
    {
        int p = 0,u = 0;
        for(auto c : s)
        {
            if(c == '#') u = 26;
            else u = c -'a';
            if(!son[p][u]) return -1;
            p = son[p][u];          
        }
        return val[p];
    }
    WordFilter(vector<string>& words) {
        int n = words.size();
        for(int i = 0 ; i <  n ; i ++)
        {
            string cur ="#" + words[i];
            insert(cur,i);
            for(int k = words[i].length() - 1; k >= 0; k --){
                cur = words[i][k] + cur;
                insert(cur,i);
            }
        }
    }

    int f(string prefix, string suffix) {
        string cur = suffix + "#" + prefix;
        return query(cur);
    }
};

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter* obj = new WordFilter(words);
 * int param_1 = obj->f(prefix,suffix);
 */