We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Palindrome Pairs

Difficulty: Hard

Problem Description

You are given a 0-indexed array of unique strings words. A palindrome pair is a pair of integers (i, j) such that:

  • 0 <= i, j < words.length,
  • i != j, and
  • words[i] + words[j] (the concatenation of the two strings) is a palindrome.

Return an array of all the palindrome pairs of words.

Key Insights

  • A palindrome reads the same forwards and backwards.
  • Concatenation of two strings can potentially form a palindrome if the first string can be complemented by the second.
  • Using a hash map (or a dictionary) can help efficiently check for potential pairs.
  • Consider edge cases such as empty strings and single-character strings.

Space and Time Complexity

Time Complexity: O(sum of words[i].length)
Space Complexity: O(n) where n is the number of words.

Solution

The solution involves using a hash map to store the words and their indices for quick lookup. For each word, we check if there exists another word that, when concatenated, would make a palindrome. The checks involve:

  1. For each word, iterate through possible splits.
  2. For each split, check if the left part is a palindrome and if the reverse of the right part exists in the hash map.
  3. Repeat the process considering the reverse, checking if the right part is a palindrome and if the left part reversed exists.

This approach ensures that we efficiently find all pairs without needing to check every possible combination explicitly.

Code Solutions

def is_palindrome(s):
    return s == s[::-1]

def palindrome_pairs(words):
    word_dict = {word: i for i, word in enumerate(words)}
    result = []
    
    for i, word in enumerate(words):
        for j in range(len(word) + 1):
            left, right = word[:j], word[j:]
            # Check left part
            if is_palindrome(left):
                rev_right = right[::-1]
                if rev_right in word_dict and word_dict[rev_right] != i:
                    result.append([word_dict[rev_right], i])
            # Check right part
            if j != len(word) and is_palindrome(right):
                rev_left = left[::-1]
                if rev_left in word_dict and word_dict[rev_left] != i:
                    result.append([i, word_dict[rev_left]])
    
    return result
← Back to All Questions