package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 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:
 Given words = ["bat", "tab", "cat"]
 Return [[0, 1], [1, 0]]
 The palindromes are ["battab", "tabbat"]
 Example 2:
 Given words = ["abcd", "dcba", "lls", "s", "sssll"]
 Return [[0, 1], [1, 0], [3, 2], [2, 4]]
 The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]
 */
public class _336 {

    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> pairs = new ArrayList();
        Map<String, Integer> map = new HashMap();
        for (int i = 0; i < words.length; i++) {
            map.put(words[i], i);
        }

        for (int i = 0; i < words.length; i++) {
            int l = 0;
            int r = 0;
            while (l <= r) {
                String s = words[i].substring(l, r);
                Integer j = map.get(new StringBuilder(s).reverse().toString());
                if (j != null && j != i && isPalindrome(words[i].substring(l == 0 ? r : 0, l == 0 ? words[i].length() : l))) {
                    pairs.add(Arrays.asList(l == 0 ? new Integer[]{i, j} : new Integer[]{j, i}));
                }
                if (r < words[i].length()) {
                    r++;
                } else {
                    l++;
                }
            }
        }
        return pairs;
    }

    private boolean isPalindrome(String s) {
        for (int i = 0; i < s.length() / 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }

}

@@ -157,16 +157,40 @@
 ap;%0A%0A/**
+336. Palindrome Pairs%0A *
 %0A * Give
@@ -676,16 +676,56 @@
 _336 %7B%0A%0A
+    public static class Solution1 %7B%0A    
     publ
@@ -789,16 +789,20 @@
         
+   
+ 
 List%3CLis
@@ -846,16 +846,20 @@
         
+    
 Map%3CStri
@@ -892,32 +892,36 @@
 hMap();%0A        
+  
+  
 for (int i = 0; 
@@ -957,16 +957,20 @@
         
+    
 map.put(
@@ -987,27 +987,35 @@
 i);%0A        
+ 
-%7D%0A%0A
+   %7D%0A%0A    
         for 
@@ -1059,24 +1059,28 @@
             
+    
 int l = 0;%0A 
@@ -1086,24 +1086,28 @@
             
+   
+ 
 int r = 0;%0A 
@@ -1101,24 +1101,28 @@
  int r = 0;%0A
+    
             
@@ -1154,16 +1154,20 @@
         
+  
+  
 String s
@@ -1195,16 +1195,20 @@
 (l, r);%0A
+    
         
@@ -1291,24 +1291,28 @@
             
+ 
+   
 if (j != nul
@@ -1339,16 +1339,41 @@
 indrome(
+%0A                        
 words%5Bi%5D
@@ -1455,16 +1455,20 @@
         
+    
 pairs.ad
@@ -1469,16 +1469,45 @@
 irs.add(
+%0A                            
 Arrays.a
@@ -1534,16 +1534,17 @@
 nteger%5B%5D
+ 
 %7Bi, j%7D :
@@ -1557,16 +1557,17 @@
 nteger%5B%5D
+ 
 %7Bj, i%7D))
@@ -1576,34 +1576,41 @@
                 
-%7D%0A
+    %7D%0A   
                 
@@ -1605,24 +1605,25 @@
             
+ 
 if (r %3C word
@@ -1659,16 +1659,20 @@
         
+    
 r++;%0A   
@@ -1684,16 +1684,20 @@
         
+  
+  
 %7D else %7B
@@ -1717,16 +1717,20 @@
         
+    
 l++;%0A   
@@ -1734,34 +1734,42 @@
                 
+ 
-%7D%0A
+   %7D%0A    
             %7D%0A  
@@ -1770,34 +1770,41 @@
   %7D%0A        
-%7D%0A
+    %7D%0A   
         
 return pairs
@@ -1787,24 +1787,25 @@
 %0A           
+ 
 return pairs
@@ -1806,16 +1806,20 @@
  pairs;%0A
+    
     %7D%0A%0A 
@@ -1821,16 +1821,20 @@
  %7D%0A%0A    
+  
+  
 private 
@@ -1862,24 +1862,28 @@
 String s) %7B%0A
+    
         for 
@@ -1929,24 +1929,28 @@
             
+ 
+   
 if (s.charAt
@@ -2000,24 +2000,28 @@
             
+    
 return false
@@ -2034,26 +2034,33 @@
         
-%7D%0A
+    %7D%0A   
         
 %7D%0A      
@@ -2043,34 +2043,39 @@
    %7D%0A           
+ 
 %7D%0A
+    
         return t
@@ -2083,13 +2083,22 @@
 ue;%0A    
+    %7D%0A    
 %7D
-%0A
 %0A%7D%0A

refactor 336