336. Palindrome Pairs

Problem:

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

Analysis:
Tire tree is not the optimal approach here.

For example. the string "ab cdc" the right part is palindrome. We want to find another string in words that is the reverse of  the left part. So we can compose a palindrome "ab cdc ba". Use hashtable to store the index of each string.

Solution:

It's important to check s2.length() != 0 to avoid duplicate.

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> res =  new ArrayList<>();
        if (words == null || words.length < 2)
            return res;
        // in hash
        Map<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++) {
            for (int j = 0; j <= words[i].length(); j++) {
                String s = words[i];
                String s1 = s.substring(0, j);
                String s2 = s.substring(j);
                
                if (isPalindrome(s1)) {
                    String s2Reverse = new StringBuilder(s2).reverse().toString();
                    if (map.containsKey(s2Reverse) && map.get(s2Reverse) != i) {
                        res.add(Arrays.asList(map.get(s2Reverse), i));
                    }
                } 
                if (s2.length() != 0 && isPalindrome(s2)) {
                    String s1Reverse = new StringBuilder(s1).reverse().toString();
                    if (map.containsKey(s1Reverse) && map.get(s1Reverse) != i) {
                        res.add(Arrays.asList(i, map.get(s1Reverse)));
                    }
                }
            }
        }
        
        return res;
    }
    
    private boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l <= r) {
            if (s.charAt(l++) != s.charAt(r--)) {
                return false;
            }
        }
        return true;
    }
}