/*
time complexity O(m * n ^ 2) where m is the length of the list and the n is the length of the word.

There are several cases to be considered that isPalindrome(s1 + s2):

Case1: If s1 is a blank string, then for any string that is palindrome s2, s1+s2 and s2+s1 are palindrome.

Case 2: If s2 is the reversing string of s1, then s1+s2 and s2+s1 are palindrome.

Case 3: If s1[0:cut] is palindrome and there exists s2 is the reversing string of s1[cut+1:] , then s2+s1 is palindrome.

Case 4: Similiar to case3. If s1[cut+1: ] is palindrome and there exists s2 is the reversing string of s1[0:cut] ,
then s1+s2 is palindrome.
*/

public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(words == null || words.length < 2) return result;
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for(int i=0; i<words.length; i++) map.put(words[i], i);
        for(int i=0; i<words.length; i++) {
            for(int j=0; j<=words[i].length(); j++) {
                String str1 = words[i].substring(0, j);
                String str2 = words[i].substring(j);
                if(isPalindrome(str1)) {
                    String str2reverse = new StringBuilder(str2).reverse().toString();
                    if(map.containsKey(str2reverse) && map.get(str2reverse) != i) {
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(map.get(str2reverse));
                        list.add(i);
                        result.add(list);
                    }
                }
                if(isPalindrome(str2)) {
                    String str1reverse = new StringBuilder(str1).reverse().toString();
                    // put str2.length()!=0 to avoid duplicates
                    if(map.containsKey(str1reverse) && map.get(str1reverse) != i && str2.length() != 0) {
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(i);
                        list.add(map.get(str1reverse));
                        result.add(list);
                    }
                }
            }
        }
        return result;
    }

    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while(left < right) {
            if(s.charAt(left++) != s.charAt(right--)) return false;
        }
        return true;
    }
}