My code:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (words == null || words.length == 0) {
            return ret;
        }
        
        Map<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++) {
            String word = words[i];
            if (isP(word)) {
                if (map.containsKey("") && map.get("") != i) {
                    List<Integer> group = new ArrayList<Integer>();
                    group.add(i);
                    group.add(map.get(""));
                    ret.add(group);
                    group = new ArrayList<Integer>();
                    group.add(map.get(""));
                    group.add(i);
                    ret.add(group);
                }
            }
            
            String r = new StringBuilder(word).reverse().toString();
            if (map.containsKey(r) && map.get(r) != i) {
                List<Integer> group = new ArrayList<Integer>();
                group.add(i);
                group.add(map.get(r));
                ret.add(group);
            }
            
            for (int k = 1; k < word.length(); k++) {
                String left = word.substring(0, k);
                String right = word.substring(k);
                if (isP(left)) {
                    String reversed = new StringBuilder(right).reverse().toString();
                    if (map.containsKey(reversed)) {
                        List<Integer> group = new ArrayList<Integer>();
                        group.add(map.get(reversed));
                        group.add(i);
                        ret.add(group);
                    }
                }
                if (isP(right)) {
                    String reversed = new StringBuilder(left).reverse().toString();
                    if (map.containsKey(reversed)) {
                        List<Integer> group = new ArrayList<Integer>();
                        group.add(i);
                        group.add(map.get(reversed));
                        ret.add(group);
                    }
                }
            }
            
        }
        
        return ret;
    }
    
    private boolean isP(String s) {
        int i = 0;
        int j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

reference:
http://www.programcreek.com/2014/05/leetcode-palindrome-pairs-java/

这道题目自己应该是可以做出来的。但是没能做出来。还是太赶了。直接看了答案。

对于一个word，要想构成 panlidrome
四种情况
1 . 其本身就是 panlindrome, 然后存在一个 “” empty string
2 . 他的reverse string 存在
3 . 分成左右两部分，left, right
反转 left, -> reversed_left, 如果也存在, 并且 right is panlindrome
那么
left + right + reversed_left
4 . 同理，对right做反转，差不多的途径，也可以得到一个panlindrome

然后遍历所有的word，利用 HashMap

Anyway, Good luck, Richardo! -- 10/09/2016