# 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.


class TrieNode:
    def __init__(self):
        self.isComplete = False
        self.leaves = {}
        self.index = []


class Trie(object):
    def __init__(self):
        self.root = TrieNode()

    # store the index info for every node
    def insert(self, word, i):
        cur = self.root
        cur.index.append(i)
        for c in word:
            if c not in cur.leaves:
                cur.leaves[c] = TrieNode()
            cur = cur.leaves[c]
            cur.index.append(i)
        cur.isComplete = True

    def find(self, word):
        cur = self.root
        for c in word:
            if c in cur.leaves:
                cur = cur.leaves[c]
            else:  # bugfixed , test case["pop"], ("pg", "pap")
                return []

        return cur.index


class WordFilter(object):

    def __init__(self, words):
        """
        :type words: List[str]
        """
        self.prefixTrie, self.suffixTrie = Trie(), Trie()
        for k, w in enumerate(words):
            self.prefixTrie.insert(w, k)
            self.suffixTrie.insert(w[::-1], k)

    def f(self, prefix, suffix):
        """
        :type prefix: str
        :type suffix: str
        :rtype: int
        """
        # bugfixed, we reverse "apple" to "elppa" and add to suffix
        # when we check suffix "le", we also need to revert it to "el", then do search
        pL, sL = self.prefixTrie.find(prefix), self.suffixTrie.find(suffix[::-1])
        if not pL or not sL:
            return -1
        for k in reversed(xrange(len(pL))):
            if pL[k] in sL:
                return pL[k]

        return -1


if __name__ == '__main__':
    obj = WordFilter(["pop"])
    print obj.f("pg", "pgp")

    obj = WordFilter(["apple"])
    print obj.f("a", "e")

    obj = WordFilter(
        ["abbbababbb", "baaabbabbb", "abababbaaa", "abbbbbbbba", "bbbaabbbaa", "ababbaabaa", "baaaaabbbb", "babbabbabb",
         "ababaababb", "bbabbababa"])
    print obj.f("", "abaa")
    print obj.f("babbab", "")
