NUHMAN.com

Introduction

LeetCode 336: Palindrome Pairs is a problem where you are asked to find all pairs of words in a list such that the concatenation of the two words forms a palindrome. This problem is a great exercise for string manipulation, understanding palindromes, and using efficient data structures like hash maps (dictionaries).

Problem Statement

Given a list of unique words, return all the palindrome pairs in the form of indices of the words. A palindrome pair is a pair of words such that their concatenation forms a palindrome. You can assume all words are unique, and there may be multiple valid pairs.

Example:

python

Input: words = ["abc","dad","dabc","cba"]
Output: [[0, 3], [3, 0]]
Explanation: The pairs that form palindromes are:
- "abc" + "cba" = "abccba" (Palindrome)
- "dabc" + "abc" = "dabcabc" (Palindrome)

Approach: Using Hash Map for Efficient Lookup

To solve this problem, we need to check all pairs of words and determine if their concatenation forms a palindrome. However, a brute force approach of checking all pairs would be inefficient, leading to an O(n^2) time complexity, which might be too slow for large inputs.

Instead, we can take advantage of a hash map (dictionary) to store the words and perform string manipulation efficiently. Here's the approach:

1. Reverse String Check: If we can reverse a word and find it in the dictionary, we can check if the pair forms a palindrome.
2. Substring Palindrome Check: For each word, we can check all of its possible prefixes and suffixes to see if the rest of the string forms a palindrome. This allows us to look for palindromes even if the words don't directly reverse to each other.
3. Efficient Lookup: Using a hash map, we can efficiently check if a reversed substring or full word exists in the list.

Key Idea:

• Use a dictionary to store words.
• For each word:
• Check if any prefix or suffix is a palindrome and if the reversed remaining substring exists in the dictionary.
• Check for the whole word’s reverse in the dictionary.

✅ Python Code

python

class Solution:
    def palindromePairs(self, words: list[str]) -> list[list[int]]:
        def is_palindrome(word):
            return word == word[::-1]
        
        word_dict = {word: i for i, word in enumerate(words)}
        result = []
        
        for i, word in enumerate(words):
            for j in range(len(word) + 1):
                prefix, suffix = word[:j], word[j:]
                
                if is_palindrome(prefix):
                    reversed_suffix = suffix[::-1]
                    if reversed_suffix in word_dict and word_dict[reversed_suffix] != i:
                        result.append([word_dict[reversed_suffix], i])
                
                if j != len(word) and is_palindrome(suffix):
                    reversed_prefix = prefix[::-1]
                    if reversed_prefix in word_dict and word_dict[reversed_prefix] != i:
                        result.append([i, word_dict[reversed_prefix]])
        
        return result

🧪 Dry Run Example

Input: words = ["abc", "dad", "dabc", "cba"]

1. Initial Setup: word_dict = {"abc": 0, "dad": 1, "dabc": 2, "cba": 3}
2. Iterating over the words:

• For word "abc" (index 0):
• Prefix "a", check if reverse of "bc" exists — no.
• Prefix "ab", check if reverse of "c" exists — no.
• Prefix "abc", check if reverse of "" exists — no.
• For word "dad" (index 1):
• Prefix "d", check if reverse of "ad" exists — no.
• Prefix "da", check if reverse of "d" exists — found "d" at index 1, continue.
• ...

After completing the checks for all words, the result will be:

Output: [[0, 3], [3, 0]]

Explanation:

• The pair ["abc", "cba"] forms the palindrome abccba.
• The pair ["dabc", "abc"] forms the palindrome dabcabc.

⏱️ Time & Space Complexity

MetricValueTime ComplexityO(n * m^2)Space ComplexityO(n * m)

• n is the number of words in the list.
• m is the average length of the words.
• For each word, we try all possible splits (which takes O(m) time), and for each split, we check if a substring is a palindrome (which takes O(m) time). Thus, the time complexity is O(n * m^2).
• The space complexity is O(n * m) due to the dictionary storing the words.

🧠 Key Takeaways

• This problem requires a good understanding of string manipulation and efficient lookup using hash maps.
• The approach efficiently handles large inputs by reducing the problem to simple substring checks and dictionary lookups.
• Palindrome checks for prefixes and suffixes help reduce unnecessary checks and speed up the algorithm.

🧱 Edge Cases

• Empty string in the list: The empty string is a palindrome, so you need to handle cases where an empty string forms a valid pair with other words.
• Single word: A single word cannot form a palindrome pair, so return an empty result.
• Words with special characters or spaces: Ensure that the function works with words containing non-alphabetical characters.

✅ Conclusion

LeetCode 336: Palindrome Pairs is a challenging problem that tests your skills in string manipulation and efficient data structure usage. By utilizing a dictionary for word lookup and checking prefixes and suffixes for palindrome properties, this solution runs efficiently in O(n * m^2) time and O(n * m) space, making it suitable for large inputs.