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

Solution

public class Solution {

    // index is inclusive
    // take care of blank string

    public List<List<Integer>> palindromePairs(String[] words) {

        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        Map<String, Integer> map = new HashMap<String, Integer>();
        for(int i = 0; i < words.length; i++) {
            map.put(words[i], i);
            if(words[i].equals("")) {
                for(int j = 0; j < words.length; j++) {
                    if(i != j && isPal(words[j], 0, words[j].length()-1)) {
                        ans.add(Arrays.asList(new Integer[]{i, j}));
                        ans.add(Arrays.asList(new Integer[]{j, i}));
                    }
                }
            }
        }

        for(int i = 0; i < words.length; i++) {
            for(int k = 1; k < words[i].length(); k++) {
                // try attach to right, smaller
                if(isPal(words[i], k, words[i].length() - 1)) {
                    String candid = reverse(words[i], 0, k - 1); 
                    if(map.containsKey(candid)) {
                        ans.add(Arrays.asList(new Integer[]{i, map.get(candid)}));
                    }
                }

                // try attach to left    
                if(isPal(words[i], 0, words[i].length() - 1 - k)) {
                    String candid = reverse(words[i], words[i].length() - k, words[i].length()-1);
                    if(map.containsKey(candid)) {
                        ans.add(Arrays.asList(new Integer[]{map.get(candid), i}));
                    }
                }   
            }

            // try equal length
            String can = reverse(words[i], 0, words[i].length() - 1);
            Integer idx = map.get(can);
            if(idx != null && idx > i) {
                ans.add(Arrays.asList(new Integer[]{i, idx}));
                ans.add(Arrays.asList(new Integer[]{idx, i}));
            }

        }

        return ans;
    }

    public String reverse(String s, int i, int j) {
        StringBuilder sb = new StringBuilder();
        for(int k = j; k >= i; k--) sb.append(s.charAt(k));
        return sb.toString();
    }

    public boolean isPal(String s, int i, int j) {
        while(i < j) if(s.charAt(i++) != s.charAt(j--)) return false;
        return true;
    }
}