"""336. Palindrome Pairs
Hard

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

Given a list of unique words, find all pairs of distinct indices (i, j) in the given
list, so that the concatenation of the two words, i.e. words[i] + words[j] is a
palindrome.

Example 1:
Input: ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]] 
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:
Input: ["bat","tab","cat"]
Output: [[0,1],[1,0]] 
Explanation: The palindromes are ["battab","tabbat"]
"""

class SolutionWordIdxDictPrefixSuffixPalindrome(object):
    def _isPalindrom(self, word):
        return word == word[::-1]

    def palindromePairs(self, words):
        """
        :type words: List[str]
        :rtype: List[List[int]]

        Time complexity: O(n*m^2), where
          - n: number of words
          - m: max length of words
        Space complexity: O(n+m).
        """
        # For each word, check if word's prefix and suffix are palindromes.
        n = len(words)
        pal_pairs = []

        # Use dict: word->idx for quick lookup.
        word_idx_d = {word: i for i, word in enumerate(words)}

        # Iterate through words, check word's prefix and reversed suffix (and vice versa).
        for word, idx in word_idx_d.items():
            m = len(word)

            for j in range(m + 1):
                prefix = word[:j]
                suffix = word[j:]

                if self._isPalindrom(prefix):
                    # If prefix and reversed suffix are palindrome, 
                    # append (reversed suffix idx, word idx).
                    rev_suffix = suffix[::-1]
                    if rev_suffix != word and rev_suffix in word_idx_d:
                        pal_pairs.append([word_idx_d[rev_suffix], idx])

                if j != m and self._isPalindrom(suffix):
                    # If suffix and reversed prefix are palindrome, 
                    # append to (word idx, reversed prefix word idx).
                    rev_prefix = prefix[::-1]
                    if rev_prefix in word_idx_d:
                        pal_pairs.append([idx, word_idx_d[rev_prefix]])

        return pal_pairs


def main():
    # Output: [[0,1],[1,0],[3,2],[2,4]] 
    words = ["abcd","dcba","lls","s","sssll"]
    print SolutionWordIdxDictPrefixSuffixPalindrome().palindromePairs(words)

    # Output: [[0,1],[1,0]] 
    words = ["bat","tab","cat"]
    print SolutionWordIdxDictPrefixSuffixPalindrome().palindromePairs(words)

    # Output: [[2,0],[2,1]] 
    words = ["bot","t","to"]
    print SolutionWordIdxDictPrefixSuffixPalindrome().palindromePairs(words)


if __name__ == '__main__':
    main()

@@ -548,35 +548,35 @@
 ass SolutionWord
-Idx
+pos
 DictPrefixSuffix
@@ -1080,19 +1080,19 @@
 : word-%3E
-idx
+pos
  for qui
@@ -1115,19 +1115,19 @@
    word_
-idx
+pos
 _d = %7Bwo
@@ -1134,15 +1134,19 @@
 rd: 
-i
+pos
  for 
-i
+pos
 , wo
@@ -1231,40 +1231,33 @@
 and 
-reversed suffix (and vice versa)
+suffix based on each char
 .%0A  
@@ -1272,19 +1272,19 @@
 r word, 
-idx
+pos
  in word
@@ -1284,19 +1284,19 @@
 in word_
-idx
+pos
 _d.items
@@ -1450,42 +1450,81 @@
     
-if self._isPalindrom(prefix):%0A    
+# If prefix is palindrome, reversed suffix in words but not current one,%0A
     
@@ -1541,22 +1541,16 @@
   # 
-If prefix a
+appe
 nd 
+(
 reve
@@ -1561,32 +1561,31 @@
  suffix 
-are palindrome, 
+pos, word pos).
 %0A       
@@ -1597,53 +1597,37 @@
     
-    # append (reversed suffix idx, word idx).
+if self._isPalindrom(prefix):
 %0A   
@@ -1726,35 +1726,35 @@
 _suffix in word_
-idx
+pos
 _d:%0A            
@@ -1784,27 +1784,27 @@
 ppend(%5Bword_
-idx
+pos
 _d%5Brev_suffi
@@ -1807,19 +1807,19 @@
 uffix%5D, 
-idx
+pos
 %5D)%0A%0A    
@@ -1834,53 +1834,68 @@
     
-if j != m and self._isPalindrom(suffix):%0A    
+# If suffix is palindrome but not '', and prefix in words, %0A
     
@@ -1912,21 +1912,25 @@
   # 
-If suffix and
+append (word pos,
  rev
@@ -1946,24 +1946,13 @@
 fix 
-are palindrome, 
+pos).
 %0A   
@@ -1968,61 +1968,48 @@
     
-    # append to (word idx, reversed prefix word idx).
+if j != m and self._isPalindrom(suffix):
 %0A   
@@ -2093,19 +2093,19 @@
 in word_
-idx
+pos
 _d:%0A    
@@ -2146,21 +2146,21 @@
 nd(%5B
-idx
+pos
 , word_
-idx
+pos
 _d%5Br
@@ -2313,35 +2313,35 @@
 int SolutionWord
-Idx
+pos
 DictPrefixSuffix
@@ -2452,35 +2452,35 @@
 int SolutionWord
-Idx
+pos
 DictPrefixSuffix
@@ -2600,11 +2600,11 @@
 Word
-Idx
+pos
 Dict

Revise to word_pos_d & enhance comments