745. Prefix and Suffix Search

Design a special dictionary with some words that searchs 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.

struct Trie {
    Trie* next[26];
    set<int> index;
    Trie() {
        memset(next, 0, sizeof(next));
    }
    void insert(const char* ch, int idx) {
        if('a' <= *ch and *ch <= 'z') {
            if(!next[*ch-'a']) next[*ch-'a'] = new Trie();
            next[*ch-'a']->insert(ch+1, idx);
        }
        index.insert(idx);
    }
    set<int> find(const char* ch) {
        if('a' <= * ch and *ch <= 'z') {
            if(!next[*ch-'a']) return {};
            return next[*ch-'a']->find(ch + 1);
        }
        return index;
    }
};
class WordFilter {
    Trie* inverseTrie;
    Trie* reverseTrie;
public:
    WordFilter(vector<string>& words) { //o(n)
        inverseTrie = new Trie();
        reverseTrie = new Trie();
        unordered_set<string> contain;
        for(int i = words.size() - 1; i >= 0; i--) {
            if(contain.count(words[i])) continue;
            contain.insert(words[i]);
            inverseTrie->insert(words[i].c_str(), i);
            reverse(words[i].begin(), words[i].end());
            reverseTrie->insert(words[i].c_str(), i);
        }
    }

    int f(string prefix, string suffix) { //o(nm)
        reverse(suffix.begin(), suffix.end());
        set<int> inverse = inverseTrie->find(prefix.c_str()), reverse = reverseTrie->find(suffix.c_str());
        auto inverseIt = inverse.rbegin(), reverseIt = reverse.rbegin();
        while(inverseIt != inverse.rend() and reverseIt != reverse.rend()) {
            if(*inverseIt == *reverseIt) return *inverseIt;
            else if(*inverseIt > *reverseIt) inverseIt = next(inverseIt);
            else reverseIt = next(reverseIt);
        }
        return -1;
    }
};

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

• different trie solution

struct Trie {
    unordered_map<char, Trie*> next;
    int index;
    Trie(int idx):index(idx) {}
    void insert(const char* ch, int idx) {
        if(('a' <= * ch and *ch <= 'z') or *ch == '#')  {
            if(!next.count(*ch)) next[*ch] = new Trie(idx);
            next[*ch]->insert(ch+1, idx);
        }
    }
    int find(const char* ch) {
        if(('a' <= * ch and *ch <= 'z') or *ch == '#') {
            if(!next.count(*ch)) return -1;
            return next[*ch]->find(ch + 1);
        }
        return index;
    }
};
class WordFilter {
    Trie* inverseTrie;
public:
    WordFilter(vector<string>& words) { //o(n^2)
        inverseTrie = new Trie(-1);
        unordered_set<string> contain;
        for(int i = words.size() - 1; i >= 0; i--) {
            if(contain.count(words[i])) continue;
            contain.insert(words[i]);
            int len = words[i].length();
            words[i] = words[i] + '#' + words[i];
            for(int j = 0; j < len; j++) {
                inverseTrie->insert(words[i].c_str() + j, i);
            }
        }
    }

    int f(string prefix, string suffix) { //o(nm)
        string str = suffix + '#' + prefix;
        return inverseTrie->find(str.c_str());
    }
};

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