# 336. Palindrome Pairs
Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.
Example 1:
Input: ["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: ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]
# Solution
Approach 1: O(NxNxL): N is the size of words; L is the average length of each word. (Time Limit Exceeded.)
Approach 2: O(NxLxL): N is the size of words; L is the average length of each word. If the length of each word is not too long.
# Code (Python)
Approach 1:
Approach 2:
# Code (C++)
Approach 1:
// Time Limit Exceeded.
class Solution {
private:
bool isPal(string s) {
int head = 0;
int tail = s.size() - 1;
while (head < tail)
{
if (s[head] != s[tail])
return false;
head++;
tail--;
}
return true;
}
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)
continue;
if (isPal(words[i] + words[j]))
{
vector<int> tmp;
tmp.push_back(i);
tmp.push_back(j);
res.push_back(tmp);
}
}
}
return res;
}
};
Approach 2:
// If the length of each word is not too long.
// * ["a",""] should be [[0,1],[1,0]].
// ["abcd","dcba"] shouldn't be [[0,1],[1,0],[0,1],[1,0]].
class Solution {
private:
bool isPal(string s) {
int head = 0;
int tail = s.size() - 1;
while (head < tail)
{
if (s[head] != s[tail])
return false;
head++;
tail--;
}
return true;
}
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
unordered_map<string,int> umap;
for (int i = 0; i < words.size(); ++i)
{
umap[words[i]] = i;
}
vector<vector<int>> res;
for (int i = 0; i < words.size(); ++i)
{
for (int j = 0; j <= words[i].size(); ++j)
{
// For each word, try getting the palindrome from its prefix.
if (j > 0 && isPal(words[i].substr(0, j))) // "j > 0" (see * above).
{
string rightRev = words[i].substr(j);
std::reverse(rightRev.begin(), rightRev.end());
if (umap.find(rightRev) != umap.end() && umap[rightRev] != i)
{
vector<int> tmp;
tmp.push_back(umap[rightRev]);
tmp.push_back(i);
res.push_back(tmp);
}
}
// Then try getting the palindrome from its suffix.
if (isPal(words[i].substr(j)))
{
string leftRev = words[i].substr(0, j);
std::reverse(leftRev.begin(), leftRev.end());
if (umap.find(leftRev) != umap.end() && umap[leftRev] != i)
{
vector<int> tmp;
tmp.push_back(i);
tmp.push_back(umap[leftRev]);
res.push_back(tmp);
}
}
}
}
return res;
}
};