336. Palindrome Pairs

Palindrome Pairs

Problem Description

Given a list of unique words, return all the pairs of the distinct indices (i, j) in the given list, so that the concatenation of the two words words[i] + words[j] is a palindrome.

 

Example 1:

Input: words = ["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: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]

Example 3:

Input: words = ["a",""]
Output: [[0,1],[1,0]]

 

Constraints:

• 1 <= words.length <= 5000
• 0 <= words[i].length <= 300
• words[i] consists of lower-case English letters.

Idea:

A naive approach here would attempt every possible pairing of words, but that would be inefficient. Instead, we can figure out what possible words would pair with each word and specifically check for those.

To do this, we'll first have to store each word in a map structure (word map), with the word as the key and the index as the value. This way, we can look up any possible matches with the current word as we iterate through words.

The next thing we'll want to do is define a helper function (isPalindrome) to check if a word is a palindrome. Rather than having to pass it a substring of a word, we can define it to take a range of indexes to check, so that we're not constantly building new strings.

As we iterate through words, then, each word will possibly match another word in one of three ways:

A blank string word will match on either side with any palindrome word. (e.g. "" will match with "abc" and vice versa)

A full word will match on either side with its backward version. (e.g. "abc" will match with "cba", and vice versa)

A partial word will match its backward version on the opposite side if the leftover portion of the word is a palindrome (e.g. "abcddd" will match with "cba" because "abc" matches with "cba" and "ddd" is a palindrome)

The first check is easy to perform. If we find a blank string, we can iterate through the entire words list and extra time searching for palindromes to match. We just need to remember not to match the blank string with itself.

For the second check, since we'll eventually iterate to the matching full word, we should only add one pair at this time, rather than both, as we'll be able to add the second ordering of the same pair when we get to the second word.

The third check is the most difficult. For this, we'll want to first reverse the current word to its backward version (BW), since we'll be matching existing frontwards words in the word map. Then we should iterate through the indexes of the word itself, testing both sides of the dividing index (j) for being a palindrome.

If a palindrome is found, then we can attempt to look up the other portion of the word in the word map. If a match is found, we can push that pair to our answer array (answer). At the end of the iteration of words, we can return an answer.

Let`s Code it:

/**
 * @param {string[]} words
 * @return {number[][]}
 */
var palindromePairs = function(words) {
    let word_map = new Map(), ans = []
    for (let i = 0; i < words.length; i++)
        word_map.set(words[i], i)
    for (let i = 0; i < words.length; i++) {
        if (words[i] === "") {
            for (let j = 0; j < words.length; j++)
                if (is_Palindrome(words[j]) && j !== i)
                    ans.push([i, j], [j, i])
            continue
        }
        let reverse_str = words[i].split("").reverse().join("")
        let res = word_map.get(reverse_str)
        if (res !== undefined && res !== i)
            ans.push([i, res])
        for (let j = 1; j < reverse_str.length; j++) {
            if (is_Palindrome(reverse_str, 0, j - 1)) {
                let res = word_map.get(reverse_str.slice(j))
                if (res !== undefined)
                    ans.push([i, res])
            }
            if (is_Palindrome(reverse_str, j)) {
                let res = word_map.get(reverse_str.slice(0,j))
                if (res !== undefined)
                    ans.push([res, i])
            }
        }
    }
    return ans
};

//check if a word is palindrome
const is_Palindrome = (word, i=0, j=word.length-1) => {
    while (i < j)
        if (word[i++] !== word[j--]) return false
    return true
}

Complexity analysis.

Time Complexity

    O(N * M^2) where N is the length of words and M is the average length of the words in words

Space Complexity

    We are using a map as an extra space, hence space complexity is O(N).

Conclusion

That’s all folks! In this post, we solved LeetCode problem #336. Palindrome Pairs

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!