LC745. Prefix and Suffix Search

class Trie:
    def __init__(self,val=0):
        self.val = val 
        self.children = {}
        self.index = -1

class WordFilter:
    # tc O(N*W*W)  N: number of words; W: max len of a word 
    def __init__(self, words: List[str]):
        self.root = Trie()
        for idx, word in enumerate(words):
            word += '#'
            for i in range(len(word)):
                cur = self.root
# make 2 concatenated word which each time the beginning of the word decrease by on ==>    apple#apple, pple#apple, ple#apple, le#apple, e#apple, #apple  
                for j in range(i,2*len(word)-1): # to avoid # in the end of word  
                    #print(word[j%len(word)])
                    if word[j%len(word)] not in cur.children:
                        node = Trie(word[j%len(word)])
                        cur.children[word[j%len(word)]] = node 
                    cur = cur.children[word[j%len(word)]]
                    cur.index = idx
     #tc O(W)   max len of a word   sc O(1)              
    def f(self, prefix: str, suffix: str) -> int:
        cur = self.root
        for ch in suffix + '#'+ prefix:
            if ch not in cur.children:
                return -1
            cur = cur.children[ch]
        return cur.index 
            


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