# 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:
Given `words` = `["bat", "tab", "cat"]`
Return `[[0, 1], [1, 0]]`
The palindromes are `["battab", "tabbat"]`

Example 2:
Given `words` = `["abcd", "dcba", "lls", "s", "sssll"]`
Return `[[0, 1], [1, 0], [3, 2], [2, 4]]`
The palindromes are `["dcbaabcd", "abcddcba", "slls", "llssssll"]`

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

``````class Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
vector<vector<int>> res;
unordered_map<string, int> m;
set<int> s;
for (int i = 0; i < words.size(); ++i) {
m[words[i]] = i;
s.insert(words[i].size());
}
for (int i = 0; i < words.size(); ++i) {
string t = words[i];
int len = t.size();
reverse(t.begin(), t.end());
if (m.count(t) && m[t] != i) {
res.push_back({i, m[t]});
}
auto a = s.find(len);
for (auto it = s.begin(); it != a; ++it) {
int d = *it;
if (isValid(t, 0, len - d - 1) && m.count(t.substr(len - d))) {
res.push_back({i, m[t.substr(len - d)]});
}
if (isValid(t, d, len - 1) && m.count(t.substr(0, d))) {
res.push_back({m[t.substr(0, d)], i});
}
}
}
return res;
}
bool isValid(string t, int left, int right) {
while (left < right) {
if (t[left++] != t[right--]) return false;
}
return true;
}
};
``````

``````class Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
vector<vector<int>> res;
unordered_map<string, int> m;
for (int i = 0; i < words.size(); ++i) m[words[i]] = i;
for (int i = 0; i < words.size(); ++i) {
int l = 0, r = 0;
while (l <= r) {
string t = words[i].substr(l, r - l);
reverse(t.begin(), t.end());
if (m.count(t) && i != m[t] && isValid(words[i].substr(l == 0 ? r : 0, l == 0 ? words[i].size() - r: l))) {
if (l == 0) res.push_back({i, m[t]});
else res.push_back({m[t], i});
}
if (r < words[i].size()) ++r;
else ++l;
}
}
return res;
}
bool isValid(string t) {
for (int i = 0; i < t.size() / 2; ++i) {
if (t[i] != t[t.size() - 1 - i]) return false;
}
return true;
}
};
``````

https://leetcode.com/discuss/91562/my-c-solution-275ms-worst-case-o-n-2

https://leetcode.com/discuss/91531/accepted-short-java-solution-using-hashmap

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation