Given a list ofuniquewords, find all pairs ofdistinctindices(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]] 

E
xplanation
: 
The palindromes are 
["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

Input: 
["bat","tab","cat"]
Output: 
[[0,1],[1,0]] 

E
xplanation
: 
The palindromes are 
["battab","tabbat"]

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        //1. "" + palindrome
        //2. abc + cba
        //3. abadef + fed
        //4. defaba + fed

        List<List<Integer>> ans = new ArrayList<>();
        if (words == null || words.length == 0) return ans;

        Map<String, Integer> hash = new HashMap<>();

        for (int i = 0; i < words.length; i++){
            hash.put(words[i], i);
        }

        //1.
        if (hash.containsKey("")){
            int index = hash.get("");
            for (int i = 0; i < words.length; i++){
                if (i == index || !isPalindrome(words[i])) continue;
                ans.add(Arrays.asList(i, index));
                ans.add(Arrays.asList(index, i));
            }
        }

        //2.
        for (int i = 0; i < words.length; i++){
            String cur = words[i];
            String reversed = reverseStr(cur);
            if (hash.containsKey(reversed)){
                int reverseIndex = hash.get(reversed);
                if (reverseIndex == i) continue;
                ans.add(Arrays.asList(i, reverseIndex));
            }
        }

        //3. and 4.
        for (int i = 0; i < words.length; i++){
            String cur = words[i];
            for (int j = 1; j < cur.length(); j++){
                if (isPalindrome(cur.substring(0, j))){
                    String post = cur.substring(j);
                    String reversePost = reverseStr(post);
                    if (hash.containsKey(reversePost)){
                        int reverseIndex = hash.get(reversePost);
                        ans.add(Arrays.asList(reverseIndex, i));
                    }
                }
                if (isPalindrome(cur.substring(j))){
                    String pre = cur.substring(0, j);
                    String reversePre = reverseStr(pre);
                    if (hash.containsKey(reversePre)){
                        int reverseIndex = hash.get(reversePre);
                        ans.add(Arrays.asList(i, reverseIndex));
                    }
                }
            }
        }

        return ans;
    }

    private String reverseStr(String inStr){
        return new StringBuilder(inStr).reverse().toString();
    }

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

        return true;
    }
}