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"]

一刷：题解
先把字符串全部存入一个hashmap<字符串, index>

如果[l,r]这段的reverse在array中存在，那么如果left左边的子串为palindrome，再在前面加上reverse段则满足要求。

Screen Shot 2017-07-29 at 14.43.22.png

如果是这种情况，如果如果[l,r]这段的reverse在array中存在，那么如果right右边的子串为palindrome，那么把[l,r]这段的reverse append在最后，就构成了满足要求的pair

public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> pairs = new LinkedList<>();
        if (words == null) return pairs;
        HashMap<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, r = 0;
            while (l <= r) {
                String s = words[i].substring(l, r);
                Integer j = map.get(new StringBuilder(s).reverse().toString());
                if (j != null && i != j && isPalindrome(words[i].substring(l == 0 ? r : 0, l == 0 ? words[i].length() : l)))//exlude l, r
                    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;
    }
}

二刷
思路同上

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> pairs = new LinkedList<>();
        if(words == null) return pairs;
        Map<String, Integer> map = new HashMap<>();
        for(int i=0; i<words.length; i++) map.put(words[i], i);
        for(int index=0; index<words.length; index++){
            String cur = words[index];
            for(int j=0; j<cur.length(); j++){
                String sub = cur.substring(0, j+1);
                StringBuilder reverse = new StringBuilder(sub).reverse();
                if(map.containsKey(reverse.toString()) && map.get(reverse.toString())!=index && isPalindrome(cur.substring(j+1)))
                    pairs.add(Arrays.asList(new Integer[]{index, map.get(reverse.toString())}));
            }
            int j = cur.length() - 1;
            for(int i=1; i<cur.length(); i++){
                String sub = cur.substring(i, j+1);
                StringBuilder reverse = new StringBuilder(sub).reverse();
                if(map.containsKey(reverse.toString()) && map.get(reverse.toString())!=index && isPalindrome(cur.substring(0, i)))
                    pairs.add(Arrays.asList(new Integer[]{map.get(reverse.toString()), index}));
            }
        }
        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;
    }
}