# Leetcode Palindrome Pairs problem solution

In this Leetcode Palindrome Pairs problem solution we have given a list of unique words, return all the pairs of the distinct indices (i, j) in the given list, so that the concatenation of the two words [i] + words[j] is a palindrome.

## Problem solution in Python.

```class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
rmap={w[::-1]:i for i,w in enumerate(words)}
res=[]
for i,wrd in enumerate(words):
rev=wrd[::-1]
if wrd in rmap:
if rmap[wrd]!=i:
res.append((i,rmap[wrd]))
for j in range(1,len(wrd)+1):
if wrd[:-j] in rmap and wrd[-j:]==rev[:j]:
res.append((i,rmap[wrd[:-j]]))
if wrd[j:] in rmap and wrd[:j]==rev[-j:]:
res.append((rmap[wrd[j:]],i))
return res
```

## Problem solution in Java.

```class Solution {
class TrieNode{
TrieNode[] children=new TrieNode[26];
int wordIndex=-1;
List<Integer> restIsPalindrome;
TrieNode(){
restIsPalindrome=new ArrayList<>();
}
}
TrieNode root=new TrieNode();
int n;
List<List<Integer>> res=new ArrayList<>();

public List<List<Integer>> palindromePairs(String[] words) {
n=words.length;

for(int i=0;i<n;i++){
}

for(int i=0;i<n;i++){
search(words[i], i);
}

return res;
}
private void search(String word, int wordIndex){
TrieNode cur=root;
char[] chs=word.toCharArray();
for(int i=0;i<chs.length;i++){
int j=chs[i]-'a';
if(cur.wordIndex != -1 && isPalindrome(chs, i, chs.length-1)){
}

if(cur.children[j] == null){
return;
}

cur=cur.children[j];
}
if(cur.wordIndex != -1 && cur.wordIndex != wordIndex){
}

for(int j:cur.restIsPalindrome){
}
}
private void add(String word, int wordIndex){
TrieNode cur=root;
char[] chs=word.toCharArray();
for(int i=chs.length-1;i>=0;i--){
int j=chs[i]-'a';
if(isPalindrome(chs, 0, i)){
}
if(cur.children[j] == null){
cur.children[j]=new TrieNode();
}

cur=cur.children[j];
}

cur.wordIndex=wordIndex;
}

private boolean isPalindrome(char[] chs, int i, int j){
while(i < j){
if(chs[i++] != chs[j--]){
return false;
}
}
return true;
}

}
```

## Problem solution in C++.

```class Solution {
public:
bool palindrome(string s){
int i=0,j=s.size()-1;
while(i<j){
if(s[i++]!=s[j--])  return false;
}
return true;
}
vector<vector<int>> palindromePairs(vector<string>& words) {
vector<vector<int>> ans;
if(words.size()<=1) return ans;
unordered_map<string,int> m;
for(int i=0;i<words.size();i++){
string rev = string(words[i].rbegin(),words[i].rend());
m[rev] = i+1;
}
for(int i=0;i<words.size();i++){
if(m[words[i]] && i+1!=m[words[i]])  ans.push_back({i,m[words[i]]-1});

for(int j=words[i].size()-1;j>=0;j--){
if(palindrome(words[i].substr(j))){
if(m[words[i].substr(0,j)]){
ans.push_back({i,m[words[i].substr(0,j)]-1});
}
}
}
for(int j=0;j<words[i].size();j++){
if(palindrome(words[i].substr(0,j+1))){
if(m[words[i].substr(j+1)]){
ans.push_back({m[words[i].substr(j+1)]-1,i});
}
}
}
}
return ans;
}
};
```