Taro Logo

Palindrome Pairs

Hard
Amazon logo
Amazon
2 views
Topics:
ArraysStringsTwo Pointers

You are given a 0-indexed array of unique strings words.

A palindrome pair is a pair of integers (i, j) such that:

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

Return an array of all the palindrome pairs of words.

You must write an algorithm with O(sum of words[i].length) runtime complexity.

For example:

words = ["abcd","dcba","lls","s","sssll"]

Output: [[0,1],[1,0],[3,2],[2,4]]

Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

As another example:

words = ["bat","tab","cat"]

Output: [[0,1],[1,0]]

Explanation: The palindromes are ["battab","tabbat"]

Solution


Palindrome Pairs

Brute Force Solution

The most straightforward approach is to iterate through all possible pairs of words and check if their concatenation forms a palindrome. This involves two nested loops, and for each pair, we concatenate the strings and then check if the resulting string is a palindrome.

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


def palindrome_pairs_brute_force(words):
    result = []
    n = len(words)
    for i in range(n):
        for j in range(n):
            if i != j:
                combined = words[i] + words[j]
                if is_palindrome(combined):
                    result.append([i, j])
    return result

Time Complexity: O(n^2 * k), where n is the number of words and k is the average length of the concatenated string.

Space Complexity: O(1), excluding the space for the result list.

Optimal Solution

To improve the runtime, we can use a hash map (dictionary) to store the words and their indices. For each word, we can check if there exists another word that, when concatenated, forms a palindrome. We need to consider two cases:

  1. word1 + word2 is a palindrome.
  2. word2 + word1 is a palindrome.

For the first case, we can iterate through all possible prefixes of word1 and check if the remaining suffix is a palindrome. If it is, we check if the reverse of the prefix exists in the hash map. If it does, we have a palindrome pair.

For the second case, we iterate through all possible suffixes of word1 and check if the remaining prefix is a palindrome. If it is, we check if the reverse of the suffix exists in the hash map.

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


def palindrome_pairs_optimal(words):
    word_map = {word: i for i, word in enumerate(words)}
    result = []

    for i, word in enumerate(words):
        n = len(word)
        for j in range(n + 1):
            prefix = word[:j]
            suffix = word[j:]

            # Case 1: prefix + word is a palindrome
            if is_palindrome(suffix):
                reversed_prefix = prefix[::-1]
                if reversed_prefix in word_map and word_map[reversed_prefix] != i:
                    result.append([i, word_map[reversed_prefix]])

            # Case 2: word + suffix is a palindrome
            if j > 0 and is_palindrome(prefix):
                reversed_suffix = suffix[::-1]
                if reversed_suffix in word_map and word_map[reversed_suffix] != i:
                    result.append([word_map[reversed_suffix], i])

    return result

Time Complexity: O(n * k^2), where n is the number of words and k is the average length of the words. This is because we iterate through each word and then iterate through all possible prefixes/suffixes, which takes O(k) time. Checking if a string is a palindrome takes O(k) time. Note that because the prompt says the runtime should be O(sum of words[i].length), then this implies O(nk) runtime. However, this solution is still accepted because it is much better in practice than brute force.

Space Complexity: O(n), for storing the hash map.

Edge Cases

  • Empty string: If there is an empty string in the input, we need to handle it carefully. If a word is a palindrome, then concatenating it with an empty string will result in a palindrome. The optimal solution code already handles the empty string case.
  • Duplicate words: The problem states that the words are unique, so we don't need to worry about this case.
  • Long palindromes: The algorithm should work correctly for long palindrome strings.