DSA
Palindrome Pairs
Trie. Time O(n² * k), Space O(n²).
Practice Here
Brute Force#
Try every ordered pair (i, j) with i ≠ j and check whether the concatenation words[i] + words[j] is a palindrome using a two-pointer scan from both ends. This is O(n² × k) where n is the number of words and k is the average word length — correct but too slow for large inputs. A trie-based optimisation can reduce this by inserting reversed words into a trie and then, for each word, searching for suffixes that form palindromes, achieving O(n × k²) time.
cpp
class Solution {
public:
bool isPalindrome(string s1, string s2)
{
string s = s1+s2;
int n = s.size();
for(int i=0;i<n/2;i++)
{
if(s[i]!=s[n-i-1])
return false;
}
return true;
}
vector<vector<int>> palindromePairs(vector<string>& words) {
vector<vector<int>> result;
for(int i=0;i<words.size();i++)
{
for(int j=0;j<words.size();j++)
{
if(i!=j)
{
if(isPalindrome(words[i], words[j]))
result.push_back({i,j});
}
}
}
return result;
}
};
| Complexity Type | Value |
|---|---|
| Time Complexity | O(n² * k) |
| Space Complexity | O(n²) (worst case) |