## # 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.

Approach 1:

Approach 2:

### # Code (C++)

Approach 1:

``````// Time Limit Exceeded.
class Solution {
private:
bool isPal(string s) {
int tail = s.size() - 1;
{
return false;
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 tail = s.size() - 1;
{
return false;
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;
}
};
``````