Solution For Palindrome Pairs

Problem description:

Given a list of words, find all pairs of unique 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:

Input: [“abcd”,”dcba”,”lls”,”s”,”sssll”] Output: [[0,1],[1,0],[3,2],[2,4]] Explanation: The palindromes are [“dcbaabcd”,”abcddcba”,”slls”,”llssssll”]

Example 2:

Input: [“bat”,”tab”,”cat”] Output: [[0,1],[1,0]] Explanation: The palindromes are [“battab”,”tabbat”]

Solution:

The brute-force approach to solve this problem would be to form all possible pairs of words from the list and check whether their concatenation is a palindrome. But that approach takes O(n^2 * k) time where n is the length of the list and k is the maximum length of the words in the list.

A better approach is to use a hash table to store the indices of the words in the list as keys and their reverse form as values. For each word in the list, we can check if its prefix or suffix is a palindrome. If the prefix is a palindrome, we look for the reverse of the remaining part of the word in the hash table. Similarly, if the suffix is a palindrome, we look for the reverse of the remaining part of the word in the hash table. If we find a match in the hash table, we add the indices to the result.

Code:

Here is the Python code for the solution:

def palindrome_pairs(words: List[str]) -> List[List[int]]:
# create a hash table to store the words and their indices
word_dict = {word:i for i, word in enumerate(words)}
result = [] for i, word in enumerate(words):
# check if the reverse of the entire word is in the hash table
if word[::-1] in word_dict and word_dict[word[::-1]] != i:
result.append([i, word_dict[word[::-1]]])
# check if the word can be split into two parts
for j in range(1, len(word)):
prefix, suffix = word[:j], word[j:] # check if the prefix is a palindrome and the reverse of the remaining part of the word is in the hash table
if prefix == prefix[::-1] and suffix[::-1] in word_dict:
result.append([word_dict[suffix[::-1]], i])
# check if the suffix is a palindrome and the reverse of the remaining part of the word is in the hash table
if suffix == suffix[::-1] and prefix[::-1] in word_dict:
result.append([i, word_dict[prefix[::-1]]])
return result

Time Complexity:

The time complexity of the algorithm is O(n * k^2) where n is the number of words in the list and k is the maximum length of the words in the list. The loop over indices i and j takes O(n^2) time in the worst case. For each word, we are checking its prefix and suffix which takes O(k) time for each part. So, the total time complexity is O(n * k^2).

Step by Step Implementation For Palindrome Pairs

public List> palindromePairs(String[] words) {
    List> result = new ArrayList<>();
 
    //edge case
    if(words == null || words.length == 0){
        return result;
    }
 
    //build the map save the index with its reverse string
    //key is the reverse string, value is the index of the key
    //"abcd", "dcba" => key = "abcd", value = 1
    Map map = new HashMap<>();
    for(int i=0; i key = "dcb", value = x
    for(int i=0; i
def palindromePairs(words):
    
    # create a dictionary with key as the word and value as the index
    word_dict = {word: i for i, word in enumerate(words)}
    
    # create an empty list to store the results
    result = []
    
    # loop through each word in the list
    for i, word in enumerate(words):
        
        # loop through each character in the word
        for j in range(len(word)+1):
            
            # get the left and right substrings
            left = word[:j]
            right = word[j:]
            
            # if the left substring is a palindrome, check if the right substring reversed is in the dictionary
            if left == left[::-1]:
                right_rev = right[::-1]
                if right_rev in word_dict and word_dict[right_rev] != i:
                    result.append([i, word_dict[right_rev]])
                    
            # if the right substring is a palindrome, check if the left substring reversed is in the dictionary        
            if right == right[::-1]:
                left_rev = left[::-1]
                if left_rev in word_dict and word_dict[left_rev] != i:
                    result.append([word_dict[left_rev], i])
                    
    return result
var palindromePairs = function(words) {
    // create a map of all the words and their reversed counterparts
    let map = {};
    for (let i = 0; i < words.length; i++) {
        map[words[i]] = i;
        map[words[i].split('').reverse().join('')] = i;
    }
    
    // create a set to store all the unique pairs
    let pairs = new Set();
    
    // iterate through each word in the array
    for (let i = 0; i < words.length; i++) {
        // iterate through each character in the word
        for (let j = 0; j <= words[i].length; j++) {
            // slice the word into two parts, left and right
            let left = words[i].slice(0, j);
            let right = words[i].slice(j);
            
            // if the left part is a palindrome and we have seen the right part before, we have a pair
            if (isPalindrome(left) && map[right] !== undefined && map[right] !== i) {
                pairs.add([i, map[right]]);
            }
            // if the right part is a palindrome and we have seen the left part before, we have a pair
            if (isPalindrome(right) && map[left] !== undefined && map[left] !== i) {
                pairs.add([map[left], i]);
            }
        }
    }
    
    // return the pairs as an array
    return [...pairs];
};

// helper function to check if a string is a palindrome
var isPalindrome = function(str) {
    return str === str.split('').reverse().join('');
};
class Solution {
public:
    vector> palindromePairs(vector& words) {
        //unordered_map m;
        //vector> res;
        //for (int i = 0; i < words.size(); ++i) m[words[i]] = i;
        //for (int i = 0; i < words.size(); ++i) {
        //    for (int j = 0; j <= words[i].size(); ++j) { // notice it should be "j <= words[i].size()"
        //        string left = words[i].substr(0, j);
        //        string right = words[i].substr(j);
        //        if (isPalindrome(left)) {
        //            string tmp = right;
        //            reverse(tmp.begin(), tmp.end());
        //            if (m.count(tmp) && m[tmp] != i) {
        //                res.push_back({m[tmp], i});
        //            }
        //        }
        //        // when j == words[i].size() && isPalindrome(right), there will be one result duplicated 
        //        // from the case "if (isPalindrome(left))" above, so we need to check "j != words[i].size()" here
        //        if (j != words[i].size() && isPalindrome(right)) {
        //            string tmp = left;
        //            reverse(tmp.begin(), tmp.end());
        //            if (m.count(tmp)) {
        //                res.push_back({i, m[tmp]});
        //            }
        //        }
        //    }
        //}
        //return res;
    }
    
    bool isPalindrome(string s) {
        int i = 0, j = s.size() - 1;
        while (i < j) {
            if (s[i++] != s[j--]) return false;
        }
        return true;
    }
};
public IList> PalindromePairs(string[] words) { // create a dictionary to store all of the words and their indices Dictionary dict = new Dictionary(); for (int i = 0; i < words.Length; i++) { dict.Add(words[i], i); } // create a list to store all of the palindrome pairs IList> pairs = new List>(); // loop through all of the words for (int i = 0; i < words.Length; i++) { // loop through all of the characters in the current word for (int j = 0; j <= words[i].Length; j++) { // get the left and right substrings string left = words[i].Substring(0, j); string right = words[i].Substring(j); // if the left substring is a palindrome, check if the reverse of the right substring is in the dictionary if (IsPalindrome(left)) { string reverse = ReverseString(right); if (dict.ContainsKey(reverse) && dict[reverse] != i) { pairs.Add(new List { dict[reverse], i }); } } // if the right substring is a palindrome, check if the reverse of the left substring is in the dictionary if (IsPalindrome(right)) { string reverse = ReverseString(left); if (dict.ContainsKey(reverse) && dict[reverse] != i && right.Length != 0) { pairs.Add(new List { i, dict[reverse] }); } } } } return pairs; } // helper function to check if a string is a palindrome public bool IsPalindrome(string s) { for (int i = 0; i < s.Length / 2; i++) { if (s[i] != s[s.Length - 1 - i]) { return false; } } return true; } // helper function to reverse a string public string ReverseString(string s) { char[] arr = s.ToCharArray(); Array.Reverse(arr); return new string(arr); }