Advanced Data Structures: Implementing Tries in C++ and Java/

...

/

Palindromes Pairs

Palindromes Pairs

Solve a hard-level problem on finding palindrome pairs using tries.

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 = ...