745. Prefix and Suffix Search (Hard) - TengnanYao/daily_leetcode GitHub Wiki

class WordFilter(object):

    def __init__(self, words):
        """
        :type words: List[str]
        """
        self.h = {}
        for i, word in enumerate(words):
            cur = self.h
            for c in word:
                if c not in cur:
                    cur[c] = {}
                cur = cur[c]
            cur["@"] = i + 1
        print(self.h)

    def f(self, prefix, suffix):
        """
        :type prefix: str
        :type suffix: str
        :rtype: int
        """
        self.result = -1
        cur = self.h
        for c in prefix:
            if c not in cur:
                return -1
            cur = cur[c]
        def dfs(prefix, suffix, cur):
            for c in cur:
                if c != "@":
                    dfs(prefix + c, suffix, cur[c])
                else:
                    if prefix[-len(suffix) : ] == suffix:
                        self.result = max(cur["@"] - 1, self.result)
        dfs(prefix, suffix, cur)
        return self.result

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