336. Palindrome Pairs

class TrieNode:
    def __init__(self):
        self.children = {}
        self.idx = -1
        self.res_palin_idx = []
class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        """  tc O(N*W*W)  sc O(NW)   W: max len of a word 
        1. create trieNode
        2. add reversed words into trie
            2.1 if at current trie node, current word's rest is palindrom ,update current node's restPalindrom list  e.g.    llabcd
            2.1 at end of each word inserted, update index at end trie node 
        3. search, for each word 
            3.1  if current char != in trie, return                                                 (3)     (4)      
            3.2  if rest of current word is palindrome, and trie node has reached to the end e.g. abcdll   dcba === > [4,3]  
            3.3  if current word has reached to the end and trie node has not reach to the end:   if at current trie node, there is rest palindrom list, update res    e.g.    abcd   dcball   ===>  dcball abcd  [2,1]
                            (1)  (2)                        
            3.4 both word and trie node have reached to the end, when trie node index is not current word's index, put their index into res e.g.   code edoc
        """
        root = TrieNode()
        res = []
        def add(word,w_idx):
            cur = root
              # note, if we do  for i,c in enumerate(word[::-1]): , the index here changed and will cause final answer wrong  
            for i in range(len(word)-1,-1,-1):
                c =  word[i]
                if self.isPalindrome(word,0,i):
                    cur.res_palin_idx.append(w_idx)
                
                if c not in cur.children:
                    cur.children[c] = TrieNode()
                

                cur = cur.children[c]# put below 
                
            #cur.res_palin_idx.append(w_idx)  #   nothing in middle 
            cur.idx = w_idx
        def find(word,idx):
            cur = root
            for i,c in enumerate(word):
#                 if c not in cur.children:
#                     return 
    
                #cur = cur.children[c]
                if cur.idx != -1 and  self.isPalindrome(word,i,len(word)-1):  # the word it self is palindrom and there is a case cached word is ""
                    res.append([idx,cur.idx])
                if c not in cur.children:
                    return 
                cur = cur.children[c] # put below 
            
            if cur.idx != -1 and cur.idx != idx:
                res.append([idx,cur.idx])
            for i in cur.res_palin_idx:
                # if i == idx:
                #     continue 
                res.append([idx,i])
                
                
                
        for i,w in enumerate(words):
            add(w,i)
        for i,w in enumerate(words):
            find(w,i)
        return res 
        
        
    def isPalindrome(self,w,i,j):
        while i < j :
            if w[i] != w[j]:
                return False
            i += 1
            j -= 1
        return True