[LeetCode] 336. Palindrome Pairs

 Problem : https://leetcode.com/problems/palindrome-pairs/

There are 3 cases can form a palindrome string.

1)  ABC + CBA

2)  CBA + [A-Palindrome-String] ABC 

3)  ABC[A-Palindrome-String]  + CBA   

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        
        def isPalindrome(w, left, right):
            while left < right:
                if w[left] != w[right]: return False
                left += 1
                right -= 1
            
            return True
        
        
        result = []
        seen = { k : v for v, k in enumerate(words) }
        lens = sorted({len(w) for w in words})
        
        for i, w in enumerate(words):
            # rw = reversed 'w'
            rw = w[::-1]
            
            # case abc -- cba
            if rw in seen and seen[rw] != i:
                result.append([i, seen[rw]])
                
            l = 0
            while lens[l] < len(rw):
                # case cba  -- ddabc                
                if isPalindrome(rw, 0, len(rw) - lens[l] - 1) and \
                   rw[len(w) - lens[l]:] in seen:
                    
                    result.append([i, seen[rw[len(w) - lens[l]:]]])
                # case abcdd -- cba
                if isPalindrome(rw, lens[l], len(rw)-1) and \
                   rw[:lens[l]] in seen:
                    result.append([seen[rw[:lens[l]]], i])
                
                l += 1
        
        return result

Use Trie to find possible suffix.

class TrieNode:
    def __init__(self, val):
        self.val = val
        self.index = -1
        self.nodes = {}


class Trie:
    def __init__(self):
        self.root = TrieNode('')
    
    def add(self, index, word):
        if not word:
            self.root.index = index
        else:
            p = self.root
            
            for w in word:
                if w in p.nodes:
                    p = p.nodes[w]
                else:
                    node = TrieNode(w)
                    p.nodes[w] = node
                    p = node
                    
            p.index = index
        
def isPalindrome(word):
    if not word: return True
    
    left, right = 0, len(word)-1
    
    while left < right and word[left] == word[right]:
        left += 1
        right -=1 
    
    return left >= right

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        trie = Trie()
        
        for index, word in enumerate(words):
            trie.add(index, word[::-1])
        
        result = []
        
        for index, word in enumerate(words):
            i = 0
            p = trie.root
                        
            # dfs
            stack = [(p, "")]
            
            while stack:
                p, suffix = stack.pop()
                
                if p.index != -1 and p.index != index and isPalindrome(word[i:] + suffix):
                    result.append((index, p.index))
                
                if not suffix and i < len(word) and word[i] in p.nodes:
                    stack.append((p.nodes[word[i]], ""))
                    i += 1
                else:
                    for n in p.nodes.values():
                        stack.append((n, n.val + suffix))
        return result

Edited on 06/13/2021. Add the Trie based solution.