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.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.
The C solution uses a brute-force approach to find all possible pairs `(i, j)` and checks if their concatenation results in a palindrome. It does this by iterating over all matches and using a helper function `isPalindrome` to verify the condition.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2 * k)
Space Complexity: O(n^2)
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.
This solution involves creating a Trie node structure to handle word entries with efficient searching capabilities.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * k^2)
Space Complexity: O(n * k)
| Approach | Complexity |
|---|---|
| Brute Force Check with Reversed Strings | Time Complexity: O(n^2 * k) |
| Using Trie Data Structure | Time Complexity: O(n * k^2) |
palindromes were tricky until I learned this • NeetCode • 158,866 views views
Watch 9 more video solutions →Practice Palindrome Pairs with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor