leetcode 745

问题

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:

1
2
3
4
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.

分析-使用Hash表

使用 unordered_map<int, vector<int>> 来分别存储每一个可能的前缀和后缀出现的位置。每次询问时，根据前缀和后缀得出两个 vector<int> ，在这两个 vector<int> 查找相同的最大元素，就是最终的答案，若无则返回 -1。注意：空串也是任意字符的前后缀。

代码-使用Hash表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class WordFilter {
public:
    unordered_map<string, vector<int>> p;
    unordered_map<string, vector<int>> s;

    WordFilter(vector<string>& words) {
        for (int i = 0; i < words.size(); ++i) {
            p[""].push_back(i);
            s[""].push_back(i);
            for (int j = 1; j <= words[i].size(); ++j) {
                p[words[i].substr(0, j)].push_back(i);
                s[words[i].substr(words[i].size()-j)].push_back(i);
            }
        }
    }
    int f(string prefix, string suffix) {
        if (p.find(prefix) == p.end() || s.find(suffix) == s.end())
            return -1;
        vector<int> &v1 = p[prefix];
        vector<int> &v2 = s[suffix];
        
        int m = v1.size(), n = v2.size();
        int i = m-1, j = n-1;
        while (i >= 0 && j >= 0) {
            if (v1[i] > v2[j]) --i;
            else if (v1[i] < v2[j]) --j;
            else return v1[i];
        }
        return -1;
    }
};

分析-使用Trie

在考虑每一个字符串的时候，我们可以将其能够产生的所有前后缀的情况组合成一个字符串插入到字典树中，比如当有 word[i]="apple" 时，我们将插入#apple、e#apple、le#apple、ple#apple、pple#apple、apple#apple 到字典树中，并在本次插入中将字典树上所有经过的路径的 weight 都置为 i。

当查询 prefix = "ap"，suffix = "le" 时，我们将在字典树中查询字符串 “le#ap”，并返回字典树中该字符串对应的weight，若字典树中不存在该字符串则返回 -1。在实现时，我们使用字符 '{' 来代替 '#'，因为 '{' 在ascii表中是字符 'z' 的后一位。

代码-使用Tire

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
struct TireNode {
    int val;
    TireNode *next[27];
    TireNode() {
        val = 0;
        memset(next, 0, sizeof(next));
    }
};

class WordFilter {
public:
    TireNode *root;
    WordFilter(vector<string>& words) {
        root = new TireNode();
        for (int i = 0; i < words.size(); ++i) {
            for (int j = 0; j <= words[i].size(); ++j) {
                string s = words[i].substr(words[i].size()-j) +"{" + words[i];
                add(root, s, 0, i);
            }
        }
    }
    
    int f(string prefix, string suffix) {
        string s = suffix + "{" + prefix;
        return find(root, s, 0);
    }
    
    void add(TireNode *root, string &s, int index, int val) {
        root->val = val;
        if (index == s.size())
            return;
        if (root->next[s[index]-'a'] == NULL)
            root->next[s[index]-'a'] = new TireNode();

        add(root->next[s[index]-'a'], s, index+1, val);
    }

    int find(TireNode *root, string &s, int index) {
        if (index == s.size())
            return root->val;
        if (root->next[s[index]-'a'] == NULL)
            return -1;
        return find(root->next[s[index]-'a'], s, index+1);
    }
};