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 */
2#include <iostream>
3#include <vector>
4#include <string>
5using namespace std;
6
7bool isPalindrome(const string& str) {
8 int left = 0, right = str.size() - 1;
9 while (left < right) {
10 if (str[left++] != str[right--]) return false;
11 }
12 return true;
13}
14
15vector<vector<int>> palindromePairs(vector<string>& words) {
16 vector<vector<int>> result;
17 int n = words.size();
18 for (int i = 0; i < n; ++i) {
19 for (int j = 0; j < n; ++j) {
20 if (i != j && isPalindrome(words[i] + words[j])) {
21 result.push_back({i, j});
22 }
23 }
24 }
25 return result;
26}The C++ implementation uses two nested loops to try all pairs and a helper function to check if the concatenated word forms a palindrome. It stores these pairs in a vector of vectors.
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 Java 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 version constructs a Trie for word reversals and performs quick lookup checks against word segments.