# Palindrome Pairs

This page explains Java solution to problem `Palindrome Pairs` using `String` data structure.

## Problem Statement

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 `words[i] + words[j]` is a palindrome.

Example 1:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class PalindromePairs {
public List<List<Integer>> palindromePairs(String[] words) {
HashMap<String, Integer> wordIndex = new HashMap<>();
for(int i = 0; i < words.length; i++) wordIndex.put(words[i], i);
List<List<Integer>> res = new ArrayList<>();

for(int i = 0; i < words.length; i++) {
String word = words[i];
for(int j = 0; j <= word.length(); j++) {
String w1 = word.substring(0, j);
String w2 = word.substring(j);

if(isPalindrome(w1)) {
String w2Reverse = reverse(w2);
if(wordIndex.containsKey(w2Reverse)) {
int k = wordIndex.get(w2Reverse);
}
}

if(isPalindrome(w2) && w2.length() != 0) {
String w1Reverse = reverse(w1);
if(wordIndex.containsKey(w1Reverse)) {
int k = wordIndex.get(w1Reverse);
}
}
}
}
return res;
}

private String reverse(String str) {
int i = 0;
int j = str.length() - 1;
char[] cArr = str.toCharArray();
while(i < j) {
char temp = cArr[i];
cArr[i] = cArr[j];
cArr[j] = temp;
i++;
j--;
}
return new String(cArr);
}

private boolean isPalindrome(String word) {
int i = 0;
int j = word.length() - 1;
while(i < j) {
if(word.charAt(i) != word.charAt(j)) return false;
i++;
j--;
}
return true;
}
}

``````

## Time Complexity

O(N * K2) Where
N is total number of elements in an input array
K is length of longest word in a word input array

## Space Complexity

O(N) Where
N is total number of elements in an input array