Search⌘ K
Home
Courses
Advanced Data Structures: Implementing Tries in C++ and Java

Palindromes Pairs

Explore methods to identify palindrome pairs formed by concatenating unique strings using trie data structures. Understand palindrome properties, apply hashmap and trie-based approaches, and analyze time and space complexities to solve algorithmic challenges efficiently.

We'll cover the following...

Problem statement

Given an array words of unique strings, return an array of index pairs (i,j)(i, j) such that arr[i]+arr[j]arr[i]+arr[j] is a palindrome.

Example 1

Sample input

words: ["efgh","aap","p","pppaa","hgfe"]

Sample output

[[0,4],[4,0],[2,1],[1,3]]

Explanation

The palindromes are:
"efghhgfe" = words[0] + words[4] = "efgh" + "hgfe"
"hgfeefgh" = words[4] + words[0] = "hgfe" + "efgh"
"paap" = words[2] + words[1] = "p" + "aap"
"aappppaa" = words[1] + words[2] = "aap" + "pppaa"

Example 2

Sample input

words: ["no","on","at"]

Sample output

[[0,1],[1,0]]

Explanation

The palindromes are:
"noon" = words[0] + words[1] = "no" + "on"
"onno" = words[4] + words[0] = "on" + "no"

Example 3

Sample input

words: ["fff",""]

Sample output

[[0,1],[1,0]]

Explanation

The palindromes are:
"fff" = words[0] + words[1] = "fff" + ""
"fff" = words[1] + words[0] = "" + "fff"

Try it yourself

Try to solve the problem yourself before reading the solution.

C++
Java
#include<iostream>

#include<vector>

using namespace std;



vector<vector<int>> findPalindromePairs(vector<string> words) {

    // your code goes here

    vector<vector<int>> answer;

    return answer;

}
Solve palindrome pairs in C++

Intuition

To solve this problem, let's first explore the properties of string pairs that form a palindrome.

Let's say that a palindrome is formed from three strings XX, YY, and ZZ.

String P=X+Y+ZP = X + Y + Z, where ZZ is the reverse of XX and YY is a palindrome in itself.

For example:
XX == "abc"
YY == "aba"
ZZ = ...