public List<List<Integer>> palindromePairs(String[] words) {
        if (words == null || words.length < 2) {
            return Collections.EMPTY_LIST;
        }
        Map<String, Integer> wordMap = new HashMap<>();
        List<List<Integer>> result = new ArrayList<>();

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

        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words[i].length(); j++) {
                String str1 = words[i].substring(0, j + 1);
                String str2 = words[i].substring(j + 1, words[i].length());
                if (isPalindrome(str2)) {
                    String revStr1 = new StringBuilder(str1).reverse().toString();
                    Integer index = wordMap.get(revStr1);
                    if (index != null) {
                        createList(i, wordMap.get(revStr1), result);
                    }
                }
                if (isPalindrome(str1)) {
                    String revStr2 = new StringBuilder(str2).reverse().toString();
                    Integer index = wordMap.get(revStr2);
                    if (index != null) {
                        createList(wordMap.get(revStr2), i, result);
                        if (revStr2.equals("")) {
                            createList(i, wordMap.get(revStr2), result);
                        }
                    }
                }
            }
        }
        return result;
    }
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.

Solution -
First keep mapping of word and its index.
Then iterate through every word and split it into every possible 2 substring. Then if first substring is palindrome
and reverse of second substring is in map means you can form a palindrome by combing this word with the word
in the map.

Time complexity is O(n*k*k)

Reference
https://leetcode.com/problems/palindrome-pairs/
src/com/interview/string/PalindromePair.java