745. Prefix and Suffix Search

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

Python

將存入Trie Tree的string做點變化，方便後續搜尋

以apple為例，實際存進Trie Tree的字串為 suffix + 分隔 + prefix

|apple
e|apple
le|apple
ple|apple
pple|apple
apple|apple

當要搜尋時，因為suffix已經被展開，所以直接以相同pattern搜尋Trie tree就可得知答案

Initial

Time: O(N * K^2) # N: numer of words; K: longest word length
Space: O(N * K^2)

Search:

Time: O(P+S) # P: prefix length; S: suffix length
Space: O(1)

class WordFilter:
    DELIMITER = '|'
    EOS = '#'
    WI = 'WI'
    def __init__(self, words: List[str]):
        trie = dict()
        for weight, word in enumerate(words):
            for i in range(len(word)+1):
                cur = trie
                cur[self.WI] = weight
                for char in word[i:] + self.DELIMITER + word:
                    cur = cur.setdefault(char, {})
                    cur[self.WI] = weight

                cur[self.EOS] = True

        self.trie = trie

    def f(self, prefix: str, suffix: str) -> int:
        cur = self.trie
        for char in suffix+self.DELIMITER+prefix:
            if char not in cur:
                return -1
            cur = cur[char]

        return cur[self.WI]

Python​

Python