Last updated on July 20th, 2024 at 04:19 am
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
Topics
Hash Table, String, Trie
Companies
Airbnb, Google
Level of Question
Hard
Palindrome Pairs LeetCode Solution
Table of Contents
Problem Statement
You are given a 0-indexed array of unique strings words.
A palindrome pair is a pair of integers (i, j) such that:
0 <= i, j < words.length,i != j, andwords[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”]
1. 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;
}
};
2. 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;
res.add(Arrays.asList(blankIdx, i));
res.add(Arrays.asList(i, blankIdx));
}
}
}
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;
res.add(Arrays.asList(i, found));
}
}
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;
res.add(Arrays.asList(found, i));
}
}
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;
res.add(Arrays.asList(i, found));
}
}
}
}
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;
}
}
3. 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
}
4. 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