Leetcode 746 Solution

class TrieNode:
    def __init__(self):
        self.val = -1
        self.children = collections.defaultdict(list)

    def update(self, val):
        self.val = max(self.val, val)


class WordFilter:
    def __init__(self, words: List[str]):
        self.root = TrieNode()
        self.root.update(len(words) - 1)

        for i, word in enumerate(words):
            j = 0
            while j <= len(word):
                target = "{}#{}".format(word[j:], word)
                node = self.root
                for ch in target:
                    if ch not in node.children:
                        node.children[ch] = TrieNode()
                    node = node.children[ch]
                    node.update(i)
                j += 1

    def f(self, prefix: str, suffix: str) -> int:
        target = "{}#{}".format(suffix, prefix)

        node = self.root
        for ch in target:
            if ch not in node.children:
                return -1
            node = node.children[ch]
        return node.val


# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(prefix,suffix)