{x}
blog image

Palindrome Pairs

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.

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

 

Example 1:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","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]]
Explanation: The palindromes are ["a","a"]

 

Constraints:

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

Solution Explanation:

This problem asks to find all pairs of indices (i, j) in a list of strings words such that the concatenation words[i] + words[j] is a palindrome. The solution needs to achieve O(sum of words[i].length) runtime complexity. This suggests an approach that avoids brute-force checking all pairs.

The most efficient solution utilizes a combination of string manipulation and a Trie data structure (although a hashmap approach is also possible and equally efficient). Let's break down the approach:

Approach:

  1. Palindrome Check: A helper function isPalindrome efficiently checks if a given substring is a palindrome. This is crucial for optimization.

  2. Reverse Dictionary (or Trie): The core idea is to pre-process the input words. We create a dictionary (or a Trie in the provided Java solution) where keys are the reverse of each word in words and the values are their original indices. This allows for fast lookups. A Trie is particularly efficient for prefix-based searches, as we'll see below.

  3. Iteration and Splitting: The algorithm iterates through each word in words. For each word, it considers all possible splits into two parts (prefix and suffix).

  4. Lookup and Palindrome Check:

    • Suffix Check: If the suffix is a palindrome, the algorithm checks if the reversed prefix exists in the reverse dictionary (or Trie). If it does, it's a palindrome pair (index from dictionary, current index).
    • Prefix Check: If the prefix is a palindrome, the algorithm checks if the reversed suffix exists. If it does, it's a palindrome pair (current index, index from dictionary).

  5. Result: The algorithm collects all found palindrome pairs and returns them.

Time Complexity Analysis:

  • Palindrome Check: isPalindrome takes O(L) time, where L is the length of the substring. This is done multiple times, but the total length of all substrings will not exceed the sum of the lengths of all words in words.

  • Dictionary Creation (or Trie Building): Creating the reverse dictionary or Trie takes O(Sum of lengths of words) time.

  • Iteration and Lookups: The main loop iterates through each word and each split point. The lookups in the dictionary (or Trie) take O(L) on average (or O(1) in the best case for Hashmap approach). Again, the total number of operations is bounded by the sum of word lengths.

Therefore, the overall time complexity is indeed O(Sum of words[i].length).

Space Complexity:

The space complexity is dominated by the reverse dictionary/Trie, which has a size proportional to the sum of the lengths of all words in the worst case (all words are reversed versions of others). Therefore, the space complexity is O(Sum of words[i].length).

Code Explanations (Python and Java):

The Python solution uses a dictionary for simplicity and efficiency. The Java solution demonstrates the Trie-based approach, which can be slightly more efficient for larger datasets but has more overhead. The general algorithm remains the same. Both solutions achieve the optimal time complexity.

Note: The provided Go and C# solutions are also efficient and follow the same general principles but use slightly different approaches for implementation details. The key idea is consistent across all languages: pre-processing the words for efficient lookups to form palindrome pairs.