Prefix and Suffix Search

hard 原题链接：https://leetcode.com/problems/prefix-and-suffix-search/

Prefix and Suffix Search

原题链接：https://leetcode.com/problems/prefix-and-suffix-search/

描述

Design a special dictionary which has some words and allows you to search the words in it by a prefix and a suffix.

Implement the WordFilter class:

• WordFilter(string[] words) Initializes the object with the words in the dictionary.

• f(string prefix, string suffix) Returns the index of the word in the dictionary which has the prefix prefix and the suffix suffix. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return -1.

例子

Input ["WordFilter", "f"] [[["apple"]], ["a", "e"]]

Output [null, 0]

Explanation WordFilter wordFilter = new WordFilter(["apple"]); wordFilter.f("a", "e"); // return 0, because the word at index 0 has prefix = "a" and suffix = 'e".

约束条件

• 1 <= words.length <= 15000

• 1 <= words[i].length <= 10

• 1 <= prefix.length, suffix.length <= 10

• words[i], prefix and suffix consist of lower-case English letters only.

• At most 15000 calls will be made to the function f.

解法一（runtime error)

class WordFilter {
public:
    vector <string> s;
    WordFilter(vector<string>& words) {
        s.assign(words.begin(), words.end());
    }
    
    int f(string prefix, string suffix) {
        for(int i=0; i<s.size(); i++){
            if(s[i].compare(0, prefix.size()-1, prefix)&&s[i].compare(s[i].size()-suffix.size()-1, suffix.size()-1, suffix)) return i;
    }
        return -1;
    }
};

["WordFilter","f","f","f","f","f","f","f","f","f","f"] [[["cabaabaaaa","ccbcababac","bacaabccba","bcbbcbacaa","abcaccbcaa","accabaccaa","cabcbbbcca","ababccabcb","caccbbcbab","bccbacbcba"]],["bccbacbcba","a"],["ab","abcaccbcaa"],["a","aa"],["cabaaba","abaaaa"],["cacc","accbbcbab"],["ccbcab","bac"],["bac","cba"],["ac","accabaccaa"],["bcbb","aa"],["ccbca","cbcababac"]]

解法二

使用Hashmap：

class WordFilter {
    public:
    unordered_map<string, int> map;
    WordFilter(vector<string>& words) {
        for(int w = words.size()-1; w >=0; w--){
            for(int i = 0; i <= 10 && i<= words[w].size(); i++){
                for(int j = 0; j <= 10 && j <= words[w].size(); j++){
                    map.insert(std::pair<string,int>(words[w].substr(0,i)+"#"+ words[w].substr(words[w].size()-j), w));
                }
            }
        }
    }
    int f(string prefix, string suffix) {
        return (map.count(prefix + "#" + suffix))? map.find(prefix + "#" + suffix)->second : -1;
    }
};

解法三

Trie方法

class TrieNode{
public:
    vector<TrieNode*> next;
    vector<int> idx_list;
    TrieNode(){
        next = vector<TrieNode*> (26, NULL);
    }
};

class Trie{
public:
    TrieNode* root;
    Trie(){
        root = new TrieNode();
    }
    void insert(string word, int idx){
        root->idx_list.push_back(idx); // Deal with empty string case
        TrieNode* cur = root;
        for(int i = 0; i < word.size(); i++){
            if(!cur->next[word[i] - 'a'])
                cur->next[word[i] - 'a'] = new TrieNode();
            cur = cur->next[word[i] - 'a'];
            cur->idx_list.push_back(idx);
        }
    }
    vector<int> find(string word){
        TrieNode* cur = root;
        for(int i = 0; i < word.size(); i++){
            cur = cur->next[word[i] - 'a'];
            if(!cur) return {};
        }
        return cur->idx_list;
    }
};

class WordFilter {
public:
    Trie* forward;
    Trie* backward;
    WordFilter(vector<string> words) {
        forward = new Trie();
        backward = new Trie();
        for(int i = 0; i < words.size(); i++){
            forward->insert(words[i], i);
            string rword = words[i];
            reverse(rword.begin(), rword.end());
            backward->insert(rword, i);
        }
    }
    
    int f(string prefix, string suffix) {
        vector<int> pre = forward->find(prefix);
        reverse(suffix.begin(), suffix.end());
        vector<int> post = backward->find(suffix);
        int i = pre.size() - 1;
        int j = post.size() - 1;
        while(i >= 0 && j >= 0){
            if(pre[i] == post[j]) return pre[i];
            else if(pre[i] > post[j]) i--;
            else j--;
        }
        return -1;
    }
};

总结