2026-01-06 19:37:48 +0300 MSK

class WordFilter:

    def __init__(self, words: List[str]):
        self.prefix = {}
        self.postfix = {}
        for i, word in enumerate(words):
            prefix = self.prefix
            for char in word:
                if char not in prefix:
                    prefix[char] = {}
                prefix = prefix[char]
            prefix[""] = i
            postfix = self.postfix
            for char in reversed(word):
                if char not in postfix:
                    postfix[char] = {}
                postfix = postfix[char]
            if "" not in postfix:
                postfix[""] = set()
            postfix[""] = i

    def f(self, pref: str, suff: str) -> int:
        prefixes, postfixes = set(), set()
        postfix, prefix = self.postfix, self.prefix
        for char in pref:
            if char not in prefix:
                return -1
            prefix = prefix[char]
        for char in reversed(suff):
            if char not in postfix:
                return -1
            postfix = postfix[char]
        postfix_queue = [postfix]
        prefix_queue = [prefix]
        while postfix_queue:
            for key, value in postfix_queue.pop().items():
                if key == "":
                    postfixes.add(value)
                else:
                    postfix_queue.append(value)
        while prefix_queue:
            for key, value in prefix_queue.pop().items():
                if key == "":
                    prefixes.add(value)
                else:
                    prefix_queue.append(value)
        res = prefixes & postfixes
        if not res:
            return -1
        return max(res)

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