[Leetcode] 745. Prefix and Suffix Search 解题报告

题目：

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.

思路：

我们定义两棵字典树，其中一棵存储正序单词，另一颗存储逆序单词。在构造函数中，我们分别将每个单词的正序和逆序加入到对应的字典树中即可。在f函数中，我们首先找到前缀为prefix的所有单词所对应的索引（其值等同于权重），然后找到后缀为suffix的所有单词所对应的索引。接着的问题就是在这两个索引列表中查找共同最大元素了。方法比较多，不过我们采用的是归并排序中的归并算法，其时间复杂度为O(m+n)，其中m和n分别是两个有序数组的长度。

代码：

class WordFilter {
public:
    WordFilter(vector<string> words) {
        forward_root = new TrieNode();
        backward_root = new TrieNode();
        for (int i = 0; i < words.size(); ++i) {
            addWord(forward_root, words[i], i);
            string rword(words[i]);
            reverse(rword.begin(), rword.end());
            addWord(backward_root, rword, i);
        }
    }
    
    int f(string prefix, string suffix) {
        vector<int> forward_indices, backward_indices;
        findPrefix(forward_root, prefix, forward_indices);
        reverse(suffix.begin(), suffix.end());
        findPrefix(backward_root, suffix, backward_indices);
        sort(forward_indices.begin(), forward_indices.end());
        sort(backward_indices.begin(), backward_indices.end());
        auto fit = forward_indices.rbegin(), rit = backward_indices.rbegin();
        while (fit != forward_indices.rend() && rit != backward_indices.rend()) {
            if (*fit == *rit) {
                return *fit;
            }
            else if (*fit > *rit) {
                ++fit;
            }
            else {
                ++rit;
            }
        }
        return -1;
    }
private:
    struct TrieNode {
        bool finished;
        int index;
        vector<TrieNode*> children;
        TrieNode() {
            finished = false;
            index = -1;
            children = vector<TrieNode*>(26, NULL);
        }
    };
    void addWord(TrieNode *root, string word, int index) {
        for (auto w : word) {
            int idx = w - 'a';
            if (root->children[idx] == NULL) {
                root->children[idx] = new TrieNode();
            }
            root = root->children[idx];
        }
        root->finished = true;
        root->index = index;
    }
    void findPrefix(TrieNode *root, string &prefix, vector<int> &indices) {
        TrieNode *node = root;
        for (int i = 0; i < prefix.size(); ++i) {
            int index = prefix[i] - 'a';
            if (node->children[index] == NULL) {
                return;
            }
            node = node->children[index];
        }
        DFS(node, indices);
    }
    void DFS(TrieNode *root, vector<int> &indices) {
        if (root == NULL) {
            return;
        }
        if (root->finished) {
            indices.push_back(root->index);
        }
        for (int i = 0; i < 26; ++i) {
            DFS(root->children[i], indices);
        }
    }
    TrieNode *forward_root, *backward_root;
};

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