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:
Givenwords=["bat", "tab", "cat"]
Return[[0, 1], [1, 0]]
The palindromes are["battab", "tabbat"]

Example 2:
Givenwords=["abcd", "dcba", "lls", "s", "sssll"]
Return[[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are["dcbaabcd", "abcddcba", "slls", "llssssll"]

Solution: 1.用hashmap存<reverse string, index>；2.对每个单词，按不同长度划分左右两半。如果left是palindrome，看hashmap中有没有candidate等于right，这样candidate| left |right是palindrome；同理，如果right是palindrome，看hashmap中有没有candidate等于left，这样left| right |candidate是palindrome。

特殊情况：["a", ""]。为了处理这种情况，用< =in for (int j=0; j < = words[i].length(); j++)。

但是，这样做会产生duplicate，比如["abcd", "dcba"]，所以规定right.length() != 0

O(n*k^2)

    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> ans = new ArrayList<>();
        if (words == null || words.length < 2) {
            return ans;
        }
        Map<String, Integer> hashmap = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            String reverse = new StringBuilder(words[i]).reverse().toString();
            hashmap.put(reverse, i);
        }
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j <= words[i].length(); j++) { //注意是<=
                String left = words[i].substring(0, j), right = words[i].substring(j);
                if (isPalindrome(left)) {
                    Integer index = hashmap.get(right);
                    if (index != null && index != i) {
                        List<Integer> temp = new ArrayList<>();
                        temp.add(index);
                        temp.add(i);
                        ans.add(temp);
                    }
                }
                //要有right.length() != 排除duplicate
                if (right.length() != 0 && isPalindrome(right)) {
                    Integer index = hashmap.get(left);
                    if (index != null && index != i) {
                        List<Integer> temp = new ArrayList<>();
                        temp.add(i);
                        temp.add(index);
                        ans.add(temp);
                    }
                }
            }
        }
        return ans;
    }
    private boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;
        while (left <= right) {
            if (str.charAt(left++) !=  str.charAt(right--)) return false;
        }
        return true;
    }

.