745. Prefix and Suffix Search

https://leetcode.com/problems/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.

对一系列词查询满足给定前缀和后缀的词的最大index。查词用Trie。但把每个可能的前缀和后缀的组合都放进trie空间会非常大。利用Trie找前缀很方便的性质，把单词不同后缀和整个单词拼在一起组成不同的新词放trie里，这样就不用针对所有可能的前缀单独放了。

代码参考自花花。

/*
 * @lc app=leetcode id=745 lang=cpp
 *
 * [745] Prefix and Suffix Search
 *
 * https://leetcode.com/problems/prefix-and-suffix-search/description/
 *
 * algorithms
 * Hard (31.50%)
 * Likes:    237
 * Dislikes: 165
 * Total Accepted:    14.2K
 * Total Submissions: 44.6K
 * Testcase Example:  '["WordFilter","f"]\n[[["apple"]],["a","e"]]'
 *
 * 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:
 * 
 * 
 * words has length in range [1, 15000].
 * For each test case, up to words.length queries WordFilter.f may be made.
 * words[i] has length in range [1, 10].
 * prefix, suffix have lengths in range [0, 10].
 * words[i] and prefix, suffix queries consist of lowercase letters only.
 * 
 * 
 * 
 * 
 */

// @lc code=start
class WordFilter {
public:
class TrieNode {
    public:
        vector<TrieNode*> children;
        bool word;
        int index;
        TrieNode(int ind): children(27, nullptr), word(false), index(ind) {}
    };
    TrieNode *root;
    void insert(const string &w, int index) {
        auto cur = root;
        for (const auto c : w) {
            const int i = c - 'a';
            if (cur->children[i] == nullptr) cur->children[i] = new TrieNode(index);
            cur = cur->children[i];
            cur->index = index;
        }
        cur->word = true;
    }

    TrieNode* find(const string &prefix) {
        auto cur = root;
        for (const auto c : prefix) {
            cur = cur->children[c - 'a'];
            if (cur == nullptr) break;
        }
        return cur;
    }

    int query(const string &prefix) {
        auto cur = find(prefix);
        if (cur == nullptr) return -1;
        return cur->index;
    }
    
    WordFilter(vector<string>& words) {
        root = new TrieNode(-1);
        for (int i = 0; i < words.size(); ++i) {
            const auto &w = words[i];
            auto key = "{" + w;
            insert(key, i);
            for (int j = 0; j < w.size(); ++j) {
                key = w[w.size() - j - 1] + key;
                insert(key, i);
            }
        }
    }
    
    int f(string prefix, string suffix) {
        return query(suffix + "{" + prefix);
    }
};

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

# Given many words, words[i] has weight i. 
# 
#  Design a class WordFilter that supports one function, WordFilter.f(String pre
# fix, String suffix). It will return the word with given prefix and suffix with m
# aximum weight. If no word exists, return -1. 
# 
#  Examples: 
# 
#  
# Input:
# WordFilter(["apple"])
# WordFilter.f("a", "e") // returns 0
# WordFilter.f("b", "") // returns -1
#  
# 
#  
# 
#  Note: 
# 
#  
#  words has length in range [1, 15000]. 
#  For each test case, up to words.length queries WordFilter.f may be made. 
#  words[i] has length in range [1, 10]. 
#  prefix, suffix have lengths in range [0, 10]. 
#  words[i] and prefix, suffix queries consist of lowercase letters only. 
#  
# 
#  
#  Related Topics Trie


# leetcode submit region begin(Prohibit modification and deletion)
class WordFilter(object):
    class Trie(object):

        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.trie = {}

        def insert(self, word, i):
            """
            Inserts a word into the trie.
            :type word: str
            :rtype: dict
            """
            cur = self.trie
            for c in word:
                if c not in cur:
                    cur[c] = {}
                cur = cur[c]
                cur['i'] = i
            return cur

        def startsWith(self, prefix):
            """
            Returns if there is any word in the trie that starts with the given prefix.
            :type prefix: str
            :rtype: int
            """
            cur = self.trie
            for c in prefix:
                if c not in cur:
                    return -1
                cur = cur[c]
            return cur['i']

    def __init__(self, words):
        """
        :type words: List[str]
        """
        self.trie = WordFilter.Trie()
        for weight, word in enumerate(words):
            t = self.trie
            t.insert(',' + word, weight)
            for i in range(len(word)):
                w = word[-i:]
                t.insert(w + ',' + word, weight)
            
    def f(self, prefix, suffix):
        """
        :type prefix: str
        :type suffix: str
        :rtype: int
        """
        return self.trie.startsWith(suffix + ',' + prefix)

# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(prefix,suffix)
# leetcode submit region end(Prohibit modification and deletion)