//    5.20
//    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 List<List<Integer>> palindromePairs(String[] words) { //Time Limit Exceeded
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words.length; j++) {
                if (i != j && twoWordIntegrateIsPalindrome(words[i],words[j])) {
                    List<Integer> tempList = new ArrayList<Integer>(Arrays.asList(i,j));
                    list.add(tempList);
                }
            }
        }
        return list;
    }
    
    static boolean twoWordIntegrateIsPalindrome(String str1, String str2) {
        StringBuffer str = new StringBuffer(str1 + str2);
        return (str1 + str2).equals(str.reverse().toString());
    }

AC版

public List<List<Integer>> palindromePairs1(String[] words) { //Time Limit Exceeded
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        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 preString = words[i].substring(0,j);
                String laString = words[i].substring(j);
                if (isPalindrome(preString)) {
                    String tempString = new StringBuffer(laString).reverse().toString();
                    if (map.containsKey(tempString) && map.get(tempString) != i) {
                        List<Integer> tempList = new ArrayList<Integer>(Arrays.asList(map.get(tempString),i));
                        list.add(tempList);
                    }
                }
                if (isPalindrome(laString)) {
                    String tempString = new StringBuffer(preString).reverse().toString();
                    if (map.containsKey(tempString) && map.get(tempString) != i && laString.length() != 0) {
                        List<Integer> tempList = new ArrayList<Integer>(Arrays.asList(i,map.get(tempString)));
                        list.add(tempList);
                    }
                }
            }
        }
        return list;
    }
    
    static boolean isPalindrome(String str) {
        String str1 = new StringBuffer(str).reverse().toString();
        return str1.equals(str);
    }