745. Prefix and Suffix Search • Algorithm Solutions

1. Description

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

2. Example

Example 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".

3. Constraints

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.

4. Solutions

My Accepted Solution

n = i_words.size(), l is the length of the word in i_words, p = i_prefix.size(), s = i_suffix.size()
Time complexity
WordFilter: O($nl^2$)
f: O(p + s)
Space complexity WordFilter: O($nl^2$)
f: O(1)

// It is hard to search for prefix + XXX + suffix, but it is easy to search for suffix + prefix
class TrieNode {
public:
    unordered_map<char, TrieNode*> childs;
    int maxIndex;

    TrieNode() : maxIndex(0) {}
};

class WordFilter {
public:
    // WordFilter(vector<string>& words)
    WordFilter(const vector<string>& i_words) {
        trieRoot = new TrieNode();
        insertTrieTree(trieRoot, i_words);
    }

    // int f(string prefix, string suffix)
    int f(const string i_prefix, const string& i_suffix) {
        auto wordToSearch = i_suffix + "#" + i_prefix;
        return getWordIndex(trieRoot, wordToSearch);
    }

private:
    TrieNode* trieRoot;

    void insertTrieTree(TrieNode* m_trieRoot, const vector<string>& i_words) {
        for (int i = 0; i < i_words.size(); ++i) {
            auto word = i_words[i];
            for (int l = 1; l <= word.size(); ++l) {
                auto suffix = word.substr(word.size() - l, l);
                auto wordToInsert = suffix + "#" + word; // use '#' to differentiate from words

                insertTrieTree(m_trieRoot, wordToInsert, i);
            }
        }
    }

    void insertTrieTree(TrieNode* m_trieRoot, const string& i_word, int index) {
        auto iter = trieRoot;
        for (auto letter : i_word) {
            if (iter->childs[letter] == nullptr) {
                iter->childs[letter] = new TrieNode();
            }

            iter = iter->childs[letter];

            iter->maxIndex = index;
        }
    }

    int getWordIndex(TrieNode* i_trieRoot, const string& i_word) {
        auto iter = i_trieRoot;
        for (auto letter : i_word) {
            if (iter->childs[letter] == nullptr) {
                return -1;
            }

            iter = iter->childs[letter];
        }

        return iter->maxIndex;
    }
};