# Palindrome Pairs LeetCode Solution

Here, We see Palindrome Pairs LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

## Problem Statement

You are given a 0-indexed array of unique strings `words`.

palindrome pair is a pair of integers `(i, j)` such that:

• `0 <= i, j < words.length`,
• `i != j`, and
• `words[i] + words[j]` (the concatenation of the two strings) is a palindrome.

Return an array of all the palindrome pairs of `words`.

You must write an algorithm with `O(sum of words[i].length)` runtime complexity.

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

Example 2:
Input: words = [“bat”,”tab”,”cat”]
Output: [[0,1],[1,0]]
Explanation: The palindromes are [“battab”,”tabbat”]

Example 3:
Input: words = [“a”,””]
Output: [[0,1],[1,0]]
Explanation: The palindromes are [“a”,”a”]

## Palindrome Pairs LeetCode Solution C++

`````` class Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
unordered_map<string, int> dict;
vector<vector<int>> ans;
for(int i = 0; i < words.size(); i++) {
string key = words[i];
reverse(key.begin(), key.end());
dict[key] = i;
}
if(dict.find("")!=dict.end()){
for(int i = 0; i < words.size(); i++){
if(i == dict[""]) continue;
if(isPalindrome(words[i])) ans.push_back({dict[""], i});
}
}
for(int i = 0; i < words.size(); i++) {
for(int j = 0; j < words[i].size(); j++) {
string left = words[i].substr(0, j);
string right = words[i].substr(j, words[i].size() - j);
if(dict.find(left) != dict.end() && isPalindrome(right) && dict[left] != i) {
ans.push_back({i, dict[left]});
}
if(dict.find(right) != dict.end() && isPalindrome(left) && dict[right] != i) {
ans.push_back({dict[right], i});
}
}
}
return ans;
}
bool isPalindrome(string str){
int i = 0;
int j = str.size() - 1;
while(i < j) {
if(str[i++] != str[j--]) return false;
}
return true;
}
};```Code language: PHP (php)```

## Palindrome Pairs LeetCode Solution Java

``````public class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(words == null || words.length == 0){
return res;
}
HashMap<String, Integer> map = new HashMap<>();
for(int i = 0; i < words.length; i++){
map.put(words[i], i);
}
if(map.containsKey("")){
int blankIdx = map.get("");
for(int i = 0; i < words.length; i++){
if(isPalindrome(words[i])){
if(i == blankIdx) continue;
}
}
}
for(int i = 0; i < words.length; i++){
String cur_r = reverseStr(words[i]);
if(map.containsKey(cur_r)){
int found = map.get(cur_r);
if(found == i) continue;
}
}
for(int i = 0; i < words.length; i++){
String cur = words[i];
for(int cut = 1; cut < cur.length(); cut++){
if(isPalindrome(cur.substring(0, cut))){
String cut_r = reverseStr(cur.substring(cut));
if(map.containsKey(cut_r)){
int found = map.get(cut_r);
if(found == i) continue;
}
}
if(isPalindrome(cur.substring(cut))){
String cut_r = reverseStr(cur.substring(0, cut));
if(map.containsKey(cut_r)){
int found = map.get(cut_r);
if(found == i) continue;
}
}
}
}
return res;
}

public String reverseStr(String str){
StringBuilder sb= new StringBuilder(str);
return sb.reverse().toString();
}
public boolean isPalindrome(String s){
int i = 0;
int j = s.length() - 1;
while(i <= j){
if(s.charAt(i) != s.charAt(j)){
return false;
}
i++;
j--;
}
return true;
}
}```Code language: JavaScript (javascript)```

## Palindrome Pairs Solution JavaScript

``````var palindromePairs = function(words) {
let wmap = new Map(), ans = []
for (let i = 0; i < words.length; i++)
wmap.set(words[i], i)
for (let i = 0; i < words.length; i++) {
if (words[i] === "") {
for (let j = 0; j < words.length; j++)
if (isPal(words[j]) && j !== i)
ans.push([i, j], [j, i])
continue
}
let bw = words[i].split("").reverse().join("")
let res = wmap.get(bw)
if (res !== undefined && res !== i)
ans.push([i, res])
for (let j = 1; j < bw.length; j++) {
if (isPal(bw, 0, j - 1)) {
let res = wmap.get(bw.slice(j))
if (res !== undefined)
ans.push([i, res])
}
if (isPal(bw, j)) {
let res = wmap.get(bw.slice(0,j))
if (res !== undefined)
ans.push([res, i])
}
}
}
return ans
};

const isPal = (word, i=0, j=word.length-1) => {
while (i < j)
if (word[i++] !== word[j--]) return false
return true
}```Code language: JavaScript (javascript)```

## Palindrome Pairs Solution Python

``````class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
wmap, ans = {}, []
for i in range(len(words)):
wmap[words[i]] = i
for i in range(len(words)):
if words[i] == "":
for j in range(len(words)):
w = words[j]
if self.isPal(w, 0, len(w)-1) and j != i:
ans.append([i, j])
ans.append([j, i])
continue
bw = words[i][::-1]
if bw in wmap:
res = wmap[bw]
if res != i: ans.append([i, res])
for j in range(1, len(bw)):
if bw[j:] in wmap and self.isPal(bw, 0, j - 1):
ans.append([i, wmap[bw[j:]]])
if bw[:j] in wmap and self.isPal(bw, j, len(bw)-1):
ans.append([wmap[bw[:j]], i])
return ans

def isPal(self, word: str, i: int, j: int) -> bool:
while i < j:
if word[i] != word[j]: return False
i += 1
j -= 1
return True```Code language: HTML, XML (xml)```
Scroll to Top