Leetcode 336. Palindrome Pairs

Problem Explanation

In this problem, we are given a list of unique words and we have to find all pairs of distinct indices (i, j) such that the concatenation of words[i] and words[j] forms a palindrome. A palindrome is a string that reads the same backwards as forwards.

A simple way to solve this problem would be to compare every pair of words and check if their concatenation forms a palindrome. However, this approach would be very inefficient.

A more efficient approach is using a hash map to store each word and its index after reversing it. We're reversing the words because if word1+word2 forms a palindrome, word1 must be the reverse of some suffix of word2 and word2 must be the reverse of some prefix of word1.

This way, when iterating through the list again, for each word, we only have to check if its left part and right part exists in our map, and if their concatenations form a palindrome.

Let's walk through an example for a better understanding:

Suppose we have the following list of words: ["abcd","dcba","lls","s","sssll"].

We map each word with its index after reversing it: {"dcba":0,"abcd":1,"sll":2,"s":3,"llsss":4}

Now, we iterate through the list again:

1. For "abcd": we have "" + "abcd" (since an empty string concatenated before any palindrome results in another palindrome), "a" + "bcddcba" ("bcddcba" is a palindrome as "a" is a prefix of "abcd"), "ab" + "cdba" ("cdba" is a palindrome as "ab" is a prefix of "abcd") and "abc" + "dba" ("dba" is not a palindrome), so we get pairs [3,0] and [1,0].
2. For "dcba": similarly, we get pairs [0,3] and [0,1].
3. For "lls": we have "" + "lls" (but "lls" is not a palindrome), "l" + "ls" ("ls" is not a palindrome), "ll" + "s" ("s" is a palindrome as "ll" is a suffix of "lls") and "lls" + "" ("lls"+"" = "lls" is not a palindrome), so we get pair [2,3].
4. For "s": we have "" + "s" ("s" is a palindrome and the empty string only has to be checked once), "s" + "" ("s" is a palindrome), so we get pair [2,3].
5. For "sssll": we get pairs [4,2].

So the final result is [[1,0],[0,1],[2,3],[4,2]].

Python Solution

Here is the Python solution based on the same approach explained above:

1
2python
3class Solution:
4    def palindromePairs(self, words):
5        def is_palindrome(check):
6            return check == check[::-1]
7            
8        words = {word: i for i, word in enumerate(words)}
9        valid_pals = []
10        for word, k in words.items():
11            for j in range(len(word)+1):
12                pref = word[:j]
13                suf = word[j:]
14                if is_palindrome(pref):
15                    back = suf[::-1]
16                    if back != word and back in words:
17                        valid_pals.append([words[back],  k])
18                if j != len(word) and is_palindrome(suf):
19                    back = pref[::-1]
20                    if back != word and back in words:
21                        valid_pals.append([k, words[back]])
22        return valid_pals

Java Solution

Here is the Java solution for the same approach:

1
2java
3class Solution {
4    public List<List<Integer>> palindromePairs(String[] words) {
5        List<List<Integer>> ret = new ArrayList<>(); 
6        if (words == null || words.length < 2) return ret;
7        Map<String, Integer> map = new HashMap<String, Integer>();
8        for (int i=0; i<words.length; i++) map.put(words[i], i);
9        for (int i=0; i<words.length; i++) {
10            //System.out.println(words[i]);
11            for (int j=0; j<=words[i].length(); j++) { // notice it should be "j <= words[i].length()"
12                String str1 = words[i].substring(0, j);
13                String str2 = words[i].substring(j);
14                if (isPalindrome(str1)) {
15                    String str2rvs = new StringBuilder(str2).reverse().toString();
16                    if (map.containsKey(str2rvs) && map.get(str2rvs) != i) {
17                        List<Integer> list = new ArrayList<Integer>();
18                        list.add(map.get(str2rvs));
19                        list.add(i);
20                        ret.add(list);
21                        //System.out.printf("isPal(str1): %s\n", list.toString());
22                    }
23                }
24                if (isPalindrome(str2)) {
25                    String str1rvs = new StringBuilder(str1).reverse().toString();
26                    // check "str.length() != 0" to avoid duplicates
27                    if (map.containsKey(str1rvs) && map.get(str1rvs) != i && str2.length()!=0) { 
28                        List<Integer> list = new ArrayList<Integer>();
29                        list.add(i);
30                        list.add(map.get(str1rvs));
31                        ret.add(list);
32                        //System.out.printf("isPal(str2): %s\n", list.toString());
33                    }
34                }
35            }
36        }
37        return ret;
38    }
39
40    private boolean isPalindrome(String str) {
41        int left = 0;
42        int right = str.length() - 1;
43        while (left <= right) {
44            if (str.charAt(left++) !=  str.charAt(right--)) return false;
45        }
46        return true;
47    }
48}

Please note, JavaScript, C++, and C# solutions are not included here.## JavaScript Solution

In JavaScript, we can use a similar approach with a hash map, and a helper function can be created to check if the string is a palindrome. Here is the JavaScript solution:

1
2javascript
3var palindromePairs = function(words) {
4    let output = [];
5    let map = {};
6    
7    // Create a helper function to check if the word is palindrome
8    let isPalindrome = (word) => {
9        let i = 0, j = word.length - 1;
10        while (i < j) {
11            if (word[i++] !== word[j--]) {
12                return false;
13            }
14        }
15        return true;
16    }
17    
18    for (let i = 0; i < words.length; i++) {
19        let word = words[i];
20        map[word] = i;
21    }
22    
23    for (let i = 0; i < words.length; i++) {
24        let word = words[i];
25        for (let j = 0; j <= word.length; j++) {
26            let word1 = word.slice(0, j);
27            let word2 = word.slice(j, word.length);
28            if (isPalindrome(word1)) {
29                let reverseWord2 = word2.split("").reverse().join("");
30                if (map[reverseWord2] && map[reverseWord2] !== i) {
31                    output.push([map[reverseWord2], i]);
32                }
33            }
34            if (word2.length > 0 && isPalindrome(word2)) {
35                let reverseWord1 = word1.split("").reverse().join("");
36                if (map[reverseWord1] && map[reverseWord1] !== i) {
37                    output.push([i, map[reverseWord1]]);
38                }
39            }
40        }
41    }
42    
43    return output;
44};

This algorithm works by first creating a map of word-to-index pairs. For every word in the list, it splits it into two at all possible points and checks if the first half is a palindrome. If it is, it finds the reverse of the second half in the map. It follows the same process if the second half is a palindrome. The indices are then stored in an output array and returned at the end.

This algorithm is more efficient than a pairwise comparison of all words, as it reduces the problem to a series of string and array operations. This makes it suitable for larger lists of words, where a naive approach would be too slow.