Palindrome Pairs
Palindrome Pairs is a hard arrays & hashing problem solved with the hashing pattern.
The best approach, optimal (hash map of reversed pieces), runs in O(n · L²) time and O(n · L) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (test every ordered pair) up.
Problem
You are given an array words of distinct lowercase strings. A palindrome pair is an ordered pair of indices (i, j) with i != j such that words[i] + words[j] (the concatenation) reads the same forwards and backwards.
Return every palindrome pair as a list [i, j]. The pairs may be returned in any order.
Examples
Example 1
- Input
words = ["top", "pot", "x", "topx", ""]- Output
[[0, 1], [1, 0], [3, 1], [2, 4], [4, 2]]- Why
- "toppot", "pottop" and "topxpot" are palindromes, and the single letter "x" works with the empty word on either side.
Example 2
- Input
words = ["ab", "cba", "ccc"]- Output
[[0, 1]]- Why
- "ab" + "cba" = "abcba" is a palindrome; the opposite order "cbaab" is not, and "ccc" fits with neither word.
Example 3
- Input
words = ["mad", "am", "z"]- Output
[[0, 1]]- Why
- "mad" + "am" = "madam" reads the same both ways. No other ordered pair does.
Constraints
1 <= words.length <= 50000 <= words[i].length <= 300words[i]consists of lowercase English letters, and all words are distinct.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (test every ordered pair) | O(n² · L) | O(1) |
| Optimal (hash map of reversed pieces) | O(n · L²) | O(n · L) |
1Brute force (test every ordered pair)
O(n² · L)n(n - 1) ordered pairs, each checked in time proportional to the combined length (at most 2L).O(1)No extra storage besides the output.For every ordered pair (i, j) with i != j, check whether words[i] + words[j] is a palindrome with two pointers that walk in from both ends of the virtual concatenation.
- For every i and every j != i:
- Let a = words[i], b = words[j]; the combined string has length a.length + b.length.
- Compare characters from both ends (reading from a or b depending on the position) until the pointers meet.
- If every comparison matches, add [i, j].
class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < words.length; i++) {
for (int j = 0; j < words.length; j++) {
if (i != j && isPal(words[i], words[j])) {
res.add(Arrays.asList(i, j));
}
}
}
return res;
}
private boolean isPal(String a, String b) {
int total = a.length() + b.length();
int l = 0, r = total - 1;
while (l < r) {
char cl = l < a.length() ? a.charAt(l) : b.charAt(l - a.length());
char cr = r < a.length() ? a.charAt(r) : b.charAt(r - a.length());
if (cl != cr) return false;
l++;
r--;
}
return true;
}
}class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
res = []
for i, a in enumerate(words):
for j, b in enumerate(words):
if i != j:
s = a + b
if s == s[::-1]:
res.append([i, j])
return resclass Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
vector<vector<int>> res;
int n = words.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j && isPal(words[i], words[j])) {
res.push_back({i, j});
}
}
}
return res;
}
private:
bool isPal(const string& a, const string& b) {
int la = a.size();
int l = 0, r = la + (int)b.size() - 1;
while (l < r) {
char cl = l < la ? a[l] : b[l - la];
char cr = r < la ? a[r] : b[r - la];
if (cl != cr) return false;
l++;
r--;
}
return true;
}
};function palindromePairs(words) {
const res = [];
const isPal = (a, b) => {
const la = a.length;
let l = 0, r = la + b.length - 1;
while (l < r) {
const cl = l < la ? a[l] : b[l - la];
const cr = r < la ? a[r] : b[r - la];
if (cl !== cr) return false;
l++;
r--;
}
return true;
};
for (let i = 0; i < words.length; i++) {
for (let j = 0; j < words.length; j++) {
if (i !== j && isPal(words[i], words[j])) res.push([i, j]);
}
}
return res;
}2Optimal (hash map of reversed pieces)
O(n · L²)Each of the n words has L + 1 cuts, and each cut does palindrome checks, reversals and hashing in O(L).O(n · L)The hash map stores all the words.Map every word to its index. Split each word w (index i) at every position into left + right. If left is a palindrome and some other word equals reverse(right), then that word placed before w gives reverse(right) + left + right, a palindrome. Symmetrically, if right is a palindrome and some other word equals reverse(left), placing it after w works. Skipping the second check when right is empty prevents reporting the same pair twice.
- Build index = {word: position}.
- For each word w at i and each cut from 0 to len(w): left = w[0..cut), right = w[cut..).
- If left is a palindrome and reverse(right) is in index at j != i, add [j, i].
- If cut < len(w), right is a palindrome and reverse(left) is in index at j != i, add [i, j].
- Return the collected pairs.
class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
Map<String, Integer> index = new HashMap<>();
for (int i = 0; i < words.length; i++) index.put(words[i], i);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < words.length; i++) {
String w = words[i];
int len = w.length();
for (int cut = 0; cut <= len; cut++) {
if (isPal(w, 0, cut - 1)) {
String need = new StringBuilder(w.substring(cut)).reverse().toString();
Integer j = index.get(need);
if (j != null && j != i) res.add(Arrays.asList(j, i));
}
if (cut < len && isPal(w, cut, len - 1)) {
String need = new StringBuilder(w.substring(0, cut)).reverse().toString();
Integer j = index.get(need);
if (j != null && j != i) res.add(Arrays.asList(i, j));
}
}
}
return res;
}
private boolean isPal(String s, int l, int r) {
while (l < r) {
if (s.charAt(l++) != s.charAt(r--)) return false;
}
return true;
}
}class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
index = {w: i for i, w in enumerate(words)}
res = []
for i, w in enumerate(words):
n = len(w)
for cut in range(n + 1):
left, right = w[:cut], w[cut:]
if left == left[::-1]:
j = index.get(right[::-1])
if j is not None and j != i:
res.append([j, i])
if cut < n and right == right[::-1]:
j = index.get(left[::-1])
if j is not None and j != i:
res.append([i, j])
return resclass Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
unordered_map<string, int> index;
for (int i = 0; i < (int)words.size(); i++) index[words[i]] = i;
vector<vector<int>> res;
for (int i = 0; i < (int)words.size(); i++) {
const string& w = words[i];
int len = w.size();
for (int cut = 0; cut <= len; cut++) {
if (isPal(w, 0, cut - 1)) {
string need = w.substr(cut);
reverse(need.begin(), need.end());
auto it = index.find(need);
if (it != index.end() && it->second != i) res.push_back({it->second, i});
}
if (cut < len && isPal(w, cut, len - 1)) {
string need = w.substr(0, cut);
reverse(need.begin(), need.end());
auto it = index.find(need);
if (it != index.end() && it->second != i) res.push_back({i, it->second});
}
}
}
return res;
}
private:
bool isPal(const string& s, int l, int r) {
while (l < r) {
if (s[l++] != s[r--]) return false;
}
return true;
}
};function palindromePairs(words) {
const index = new Map();
words.forEach((w, i) => index.set(w, i));
const isPal = (s, l, r) => {
while (l < r) {
if (s[l++] !== s[r--]) return false;
}
return true;
};
const rev = (s) => s.split("").reverse().join("");
const res = [];
for (let i = 0; i < words.length; i++) {
const w = words[i];
const len = w.length;
for (let cut = 0; cut <= len; cut++) {
if (isPal(w, 0, cut - 1)) {
const j = index.get(rev(w.substring(cut)));
if (j !== undefined && j !== i) res.push([j, i]);
}
if (cut < len && isPal(w, cut, len - 1)) {
const j = index.get(rev(w.substring(0, cut)));
if (j !== undefined && j !== i) res.push([i, j]);
}
}
}
return res;
}Edge cases to test
- The empty string pairs, in both orders, with every word that is itself a palindrome
- A word and its exact reverse form two pairs, one in each order
- A shorter word can match a longer one when the leftover middle of the longer word is a palindrome, like "pot" placed after "topx"
- A single word: no pairs at all
- A word never pairs with itself, even if it is a palindrome
Hints
Hint 1
Checking every ordered pair works, but with 5000 words that is 25 million concatenations of up to 600 characters.
Hint 2
Suppose words[j] + words[i] is a palindrome and words[j] is the shorter one. Then words[i] splits into a part that is a palindrome on its own and a part that is exactly the reverse of words[j].
Hint 3
Put every word in a hash map. For each word and each split point, test whether one side is a palindrome and look up the reverse of the other side.
FAQ
What is the best time complexity for Palindrome Pairs?
Optimal (hash map of reversed pieces) runs in O(n · L²) time and O(n · L) extra space. Each of the n words has L + 1 cuts, and each cut does palindrome checks, reversals and hashing in O(L).
Which pattern does Palindrome Pairs use?
It is a arrays & hashing problem that uses the hashing pattern. Other problems with the same pattern: Group Anagrams, First Unique Character in a String, Number of Matching Subsequences.
Is there a brute force solution for Palindrome Pairs?
Yes. Brute force (test every ordered pair) takes O(n² · L) time and O(1) space. For every ordered pair (i, j) with i != j, check whether words[i] + words[j] is a palindrome with two pointers that walk in from both ends of the virtual concatenation.
Which edge cases should I test for Palindrome Pairs?
The empty string pairs, in both orders, with every word that is itself a palindrome; A word and its exact reverse form two pairs, one in each order; A shorter word can match a longer one when the leftover middle of the longer word is a palindrome, like "pot" placed after "topx"; A single word: no pairs at all; A word never pairs with itself, even if it is a palindrome.