Last updated on January 14th, 2025 at 06:15 am
Here, we see a Palindrome Pairs LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Hash Table, String, Trie
Companies
Airbnb, Google
Level of Question
Hard
Palindrome Pairs LeetCode Solution
Table of Contents
1. 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”]
2. Coding Pattern Used in Solution
The coding pattern used in this code is “Palindrome Partitioning” or “Palindrome Matching”. This pattern involves checking for palindromic substrings and matching them with other strings to form valid palindrome pairs. The code uses hash maps for efficient lookups and string manipulation to reverse strings and check for palindromes.
3. Code Implementation in Different Languages
3.1 Palindrome Pairs 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;
}
};
3.2 Palindrome Pairs 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.3 Palindrome Pairs 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
}
3.4 Palindrome Pairs 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
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n * k²) | O(n * k) |
| Java | O(n * k²) | O(n * k) |
| JavaScript | O(n * k²) | O(n * k) |
| Python | O(n * k²) | O(n * k) |
where, n is the number of words and k is the average word length.
- Hash map construction is O(n * k), and substring checks are O(k²) for each word.
- The code efficiently finds all palindrome pairs using a combination of hash maps and substring checks.
- The time complexity is quadratic in terms of the word length due to substring operations.
- The space complexity is linear in terms of the total input size.