99클럽 코테 스터디 15/99일차 TIL #prefix-and-suffix-search(미들러)

 

class WordFilter:
    def __init__(self, words: list[str]):
        self.trie = {}
        for index, word in enumerate(words):
            length = len(word)
            # Insert all prefix and suffix combinations into the trie
            for i in range(length + 1):
                for j in range(length + 1):
                    prefix_suffix = word[:i] + '#' + word[-j:]
                    node = self.trie
                    for char in prefix_suffix:
                        if char not in node:
                            node[char] = {}
                        node = node[char]
                    node['#'] = index

    def f(self, pref: str, suff: str) -> int:
        prefix_suffix = pref + '#' + suff
        node = self.trie
        for char in prefix_suffix:
            if char not in node:
                return -1
            node = node[char]
        return node.get('#', -1)

# # Example usage:
# wordFilter = WordFilter(["apple"])
# print(wordFilter.f("a", "e"))  # Output: 0