给定一组独特的单词, 找出在给定列表中不同 的索引对(i, j),使得关联的两个单词,例如:words[i] + words[j]形成回文。
示例 1:
给定 words = ["bat", "tab", "cat"]
返回 [[0, 1], [1, 0]]
回文是 ["battab", "tabbat"]
示例 2:
给定 words = ["abcd", "dcba", "lls", "s", "sssll"]
返回 [[0, 1], [1, 0], [3, 2], [2, 4]]
回文是 ["dcbaabcd", "abcddcba", "slls", "llssssll"]

详见:https://leetcode.com/problems/palindrome-pairs/description/

C++:

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;
}
};

参考:https://leetcode.com/problems/palindrome-pairs/description/

05-13 10:44