@@ -0,0 +1,1832 @@
+# Time:  O(m + n), m is the number of prefix match, n is the number of suffix match%0A# Space: O(t * w), t is the number of nodes in trie, w is the number of words%0A%0Aclass WordFilter(object):%0A%0A    def __init__(self, words):%0A        %22%22%22%0A        :type words: List%5Bstr%5D%0A        %22%22%22%0A        def insert(trie, word, i):%0A            def add_word(cur, i):%0A                if %22_words%22 not in cur:%0A                    cur%5B%22_words%22%5D = %5B%5D%0A                cur%5B%22_words%22%5D.append(i)%0A                %0A            cur = trie%0A            add_word(cur, i)%0A            for c in word:%0A                cur = cur%5Bc%5D%0A                add_word(cur, i)%0A                %0A        _trie = lambda: collections.defaultdict(_trie)%0A        self.__prefix_trie = _trie()%0A        self.__suffix_trie = _trie()%0A        for i in reversed(xrange(len(words))):%0A            insert(self.__prefix_trie, words%5Bi%5D, i)%0A            insert(self.__suffix_trie, words%5Bi%5D%5B::-1%5D, i)%0A%0A    def f(self, prefix, suffix):%0A        %22%22%22%0A        :type prefix: str%0A        :type suffix: str%0A        :rtype: int%0A        %22%22%22%0A        def find(trie, word):%0A            cur = trie%0A            for c in word:%0A                if c not in cur:%0A                    return %5B%5D%0A                cur = cur%5Bc%5D%0A            return cur%5B%22_words%22%5D%0A        %0A        prefix_match = find(self.__prefix_trie, prefix)%0A        suffix_match = find(self.__suffix_trie, suffix%5B::-1%5D)%0A        i, j = 0, 0%0A        while i != len(prefix_match) and j != len(suffix_match):%0A            if prefix_match%5Bi%5D == suffix_match%5Bj%5D:%0A                return prefix_match%5Bi%5D%0A            elif prefix_match%5Bi%5D %3E suffix_match%5Bj%5D:%0A                i += 1%0A            else:%0A                j += 1%0A        return -1%0A        %0A%0A%0A# Your WordFilter object will be instantiated and called as such:%0A# obj = WordFilter(words)%0A# param_1 = obj.f(prefix,suffix)%0A

Create prefix-and-suffix-search.py