Table of Contents
Palindrome Pairs – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
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"]
Example 3:
Input: words = ["a",""] Output: [[0,1],[1,0]]
Constraints:
1 <= words.length <= 50000 <= words[i].length <= 300words[i]consists of lower-case English letters.
C++ Palindrome Pairs LeetCode Solution
class Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
unordered_map<string, int> dict;
vector<vector<int>> ans;
// build dictionary
for(int i = 0; i < words.size(); i++) {
string key = words[i];
reverse(key.begin(), key.end());
dict[key] = i;
}
// edge case: if empty string "" exists, find all palindromes to become pairs ("", self)
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}); // 1) if self is palindrome, here ans covers concatenate("", self)
}
}
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]}); // 2) when j = 0, left = "", right = self, so here covers concatenate(self, "")
}
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;
}
};
Java Palindrome Pairs LeetCode Solution
class Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
unordered_map<string, int> dict;
vector<vector<int>> ans;
// build dictionary
for(int i = 0; i < words.size(); i++) {
string key = words[i];
reverse(key.begin(), key.end());
dict[key] = i;
}
// edge case: if empty string "" exists, find all palindromes to become pairs ("", self)
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}); // 1) if self is palindrome, here ans covers concatenate("", self)
}
}
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]}); // 2) when j = 0, left = "", right = self, so here covers concatenate(self, "")
}
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;
}
};
Python 3 Palindrome Pairs LeetCode Solution
def is_palindrome(check):
return check == check[::-1]
words = {word: i for i, word in enumerate(words)}
valid_pals = []
for word, k in words.iteritems():
n = len(word)
for j in range(n+1):
pref = word[:j]
suf = word[j:]
if is_palindrome(pref):
back = suf[::-1]
if back != word and back in words:
valid_pals.append([words[back], k])
if j != n and is_palindrome(suf):
back = pref[::-1]
if back != word and back in words:
valid_pals.append([k, words[back]])
return valid_pals
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
Leave a comment below
