Palindrome Pairs

Example:

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

Algorithm:

1 Since we need return a list of lists, containing indices whose words if we combine shall result in a palindrome, it makes intuitive sense to have a mapping between words in the given array and their corresponding indices. Therefore lets populate a hash map with the words and their indices.

2 For each unique word in the words array, consider the word to be divided into two substrings, str1 and str2, with str1 progressively increasing from "" (empty) substring to the entire word while str2 assumes the remaining part of the word. Check if str1 is a palindrome and if so then there is a possibility of it functioning as the pivot around which a palindrome could be formed. In order to determine whether a palindrome could be indeed formed, determine whether the reverse of the str2 exists within the map and does not correspond to the current index in contention (as is the case in case str2 is "aa" in which case reverse of str2 is also "aa" and hence can correspond to the current index in the map), so as to function as a prefix to form a palindrome with str1 as the pivot.

3 If the reversed string is indeed present in the map and does not correspond to the current index, then you have got one pair of palindromes that can be added to the result list of lists. Create a temporary list, and add the prefix reversed string's index to the temp list first, followed by current index i and add the temp list to the resultant list of lists.

4 Now like wise check if str2 is a palindrome, in which case it can function as a pivot around which a palindrome can be formed. Check if the str1's reverse is present in the map and does not correspond to the current index. Also in order to consider the corner case of "" empty string being one of the words in the array, there is a need to iterate until the length of word[i] inclusive. But this may lead to empty string "" being considered in str2 as a duplicate in addition to being considered initially in str1. Therefore care must be taken to ensure that str2 is not equal to empty string to avoid duplicates. If all the above checks are satisfied, then create a temp list, add the prefix index i and the suffix index from the map corresponding to the reversed str1, and add the temp list to result list of lists. After iterating through the entire words list, return the result list of lists.

Test:

1 Test with empty words in the words array.

2 Test with no palindrome pairs.

3 Test with words containing the same letter but increasing length like ["a", "aa"]

Solution:

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
    //result list of lists
    List<List<Integer>> res = new ArrayList<>();

    if(words == null || words.length < 2) 
        return res;

    //declare hashmap
    HashMap<String, Integer> map = new HashMap<>();

    
    //map each word and its index in hashmap
    for (int i = 0; i < words.length; i++) {
        map.put(words[i], i); 
    }

    //iterate over words array
    for (int i = 0; i < words.length; i++) {
       //iterate over each letter in each word; <= to take into account "" word
    for (int j = 0; j <= words[i].length(); j++) {
            //substring 1
            String str1 = words[i].substring(0, j);
            //substring 2; remaining part of the words[i]
            String str2 = words[i].substring(j);

            if (isPalindrome(str1)) {
              
                String str2revs = new StringBuilder(str2).reverse().toString();
                if (map.containsKey(str2revs) && map.get(str2revs) != i) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(map.get(str2revs));
                    temp.add(i);
                    res.add(temp);
                 } 
            }

            if (isPalindrome(str2)) {
               String str1revs = new StringBuilder(str1).reverse().toString();
               if (map.containsKey(str1revs) && map.get(str1revs) != i && str2.length() != 0) {
                   List<Integer> temp = new ArrayList<>();
                   temp.add(i);
                   temp.add(map.get(str1revs));
                   res.add(temp);
               } 
            }
        }
    }
    return res;

    // T O(nk^2) n length of words, 
//k avg/worst case length of each word S O(n)
//k^2 coz of substring and reverse both costs k each 
}

private boolean isPalindrome (String word) {

int left = 0;
int right = word.length() - 1;
while(left <= right) {
if(word.charAt(left++) != word.charAt(right--)) return false;
}
return true;
}

}

//https://gist.github.com/harycane/edd627614dfa4d2b369001b41f48bd4c

Complexity Analysis:

Assuming size of words array is n and each word in the worst case has a length of k, then iterating through each word to form the substrings and reversing each word incurs cost of k therefore in total k^2. In addition since we iterate through the words array an additional factor of n is incurred. So in total time complexity incurred is T O(nk^2). Space complexity is S O(n), for we map the size of words array onto the hash map.