LeetCode - Palindrome Pairs

PalindromePairs.java

// 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 1 --- hashmap
public List<List<Integer>> palindromePairs(String[] words) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if(words.length == 0) return res;
    
    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++){
        for(int j = 0; j <= words[i].length(); j++){
            String str1 = words[i].substring(0 , j);
            String str2 = words[i].substring(j);
            
            if(isPalindrome(str1)){
                String str2_reverse = new StringBuilder(str2). reverse().toString();
                if(map.containsKey(str2_reverse) && map.get(str2_reverse) != i){
                    addToList(res, map.get(str2_reverse), i);
                }
            }
            // check "str2.length() != 0" to avoid duplicates
            if(str2.length() != 0 && isPalindrome(str2)){
                String str1_reverse = new StringBuilder(str1). reverse().toString();
                if(map.containsKey(str1_reverse) && map.get(str1_reverse) != i){
                    addToList(res, i, map.get(str1_reverse));
                }
            }
        }
    }
    return res;
}

private boolean isPalindrome(String str){
    int left = 0, right = str.length() - 1;
    while(left < right){
        if(str.charAt(left) != str.charAt(right)) return false;
        left++; right --;
    }
    return true;
}

private void addToList(List<List<Integer>> res, int i, int j){
    List<Integer> lst = new ArrayList<Integer>();
    lst.add(i);
    lst.add(j);
    res.add(lst);
}

// solution 2 --- use trie  https://leetcode.com/discuss/91429/solution-with-structure-total-number-words-average-length