# 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:
class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
# idea: put each word reversed in a set. For each word,
# enumerate all prefixes, if prefix in the set and the rest is palindrome, word + reverse(prefix)
# enumerate all postfixes, if postfix in the set and rest is palindrome, reverse(postfix) + word
all_reversed = { word[::-1]: i for i, word in enumerate(words) }
result = set()
for i, word in enumerate(words):
all_reversed.pop(word[::-1])
for j in range(len(word) + 1):
prefix = word[:j]
if prefix in all_reversed and self._is_palindrome(word, j, len(word) - 1):
result.add((i, all_reversed[prefix]))
postfix = word[len(word)-j:len(word)]
if postfix in all_reversed and self._is_palindrome(word, 0, len(word) - j - 1):
result.add((all_reversed[postfix], i))
all_reversed[word[::-1]] = i
return list(result)
def _is_palindrome(self, word, start, end):
while start < end:
if word[start] != word[end]:
return False
start += 1
end -= 1
return True
# 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;
}
};