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, andwords[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 <= 50000 <= words[i].length <= 300words[i] consists of lowercase English letters.The Palindrome Pairs problem asks you to find all pairs of indices where the concatenation of two words forms a palindrome. A common strategy is to use a hash map to store each word and its index, allowing fast lookup of reversed strings. For every word, split it into all possible prefix and suffix combinations. If the prefix is a palindrome, check whether the reversed suffix exists in the map. Similarly, if the suffix is a palindrome, check for the reversed prefix. This ensures all valid pair combinations are considered.
Another advanced approach uses a Trie built from reversed words. The Trie helps efficiently match prefixes while tracking indices of words whose remaining substrings are palindromes. This reduces redundant comparisons when scanning characters.
In general, the optimized hash-based solution runs in about O(n * k^2) time where n is the number of words and k is the maximum word length. Space complexity depends on storing the words or Trie nodes.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map with Prefix/Suffix Checks | O(n * k^2) | O(n * k) |
| Trie-Based Matching | O(n * k^2) | O(n * k) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Checking every two pairs will exceed the time limit. It will be O(n^2 * k). We need a faster way.
If we hash every string in the array, how can we check if two pairs form a palindrome after the concatenation?
We can check every string in words and consider it as words[j] (i.e., the suffix of the target palindrome). We can check if there is a hash of string that can be the prefix to make it a palindrome.
In this method, iterate through all possible pairs of words, concatenate them, and check if the concatenated result is a palindrome. Additionally, use the property that a string and its reverse can help identify palindrome pairs more efficiently.
Time Complexity: O(n^2 * k)
Space Complexity: O(n^2)
1/* C# Solution for Brute Force Check with Reversed Strings */
2using System;
3using System.Collections.Generic;
4
5public class Solution {
6 public bool IsPalindrome(string str) {
7 int left = 0, right = str.Length - 1;
8 while (left < right) {
9 if (str[left++] != str[right--]) return false;
10 }
11 return true;
12 }
13
14 public IList<IList<int>> PalindromePairs(string[] words) {
15 IList<IList<int>> result = new List<IList<int>>();
16 for (int i = 0; i < words.Length; ++i) {
17 for (int j = 0; j < words.Length; ++j) {
18 if (i != j && IsPalindrome(words[i] + words[j])) {
19 result.Add(new List<int>{i, j});
20 }
21 }
22 }
23 return result;
24 }
25}The C# solution checks all word pairs using nested loops and employs a helper method `IsPalindrome` to determine if they form palindromes. The results are added to a list of lists.
Instead of brute force, we can utilize a Trie data structure to store word reversals, which allows faster lookup for potential palindrome content between pairs. This method improves efficiency by focusing on checks only where relevant.
Time Complexity: O(n * k^2)
Space Complexity: O(n * k)
1/* Trie-based C++ Solution omitted due to complexity */
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Palindrome Pairs is considered a challenging string problem and has appeared in technical interviews at large tech companies. It tests understanding of string manipulation, hashing, and advanced data structures like Tries.
The most common optimal approach uses a hash map storing each word's index. For every word, split it into all possible prefix and suffix combinations and check if the remaining part forms a palindrome while the reversed counterpart exists in the map.
Hash tables and Tries are the most effective data structures. Hash maps allow fast lookup of reversed strings, while Tries help efficiently match prefixes and track palindrome suffixes during traversal.
Checking prefixes and suffixes ensures that when two words are concatenated, the remaining unmatched portion still forms a palindrome. This strategy helps discover all valid combinations without brute-forcing every pair.
This solution involves using a Trie to reverse words and manage lookup times, offering a more streamlined solution over brute force.