Leetcode 746 Solution

This article provides solution to leetcode question 746 (prefix-and-suffix-search)
Categories:
Tags:
Access this page by simply typing in "lcs 746" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/prefix-and-suffix-search

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)