0336. Palindrome Pairs¶
题目信息¶
- 题号:
0336
- 难度:
Hard
- 主题:
字符串数组、下标对、字符串拼接、回文
- 原题:
- 重点:
i与j必须不同、拼接顺序影响结果、空字符串可以参与、返回所有有序下标对
题目重述¶
给定互不相同的字符串数组 words,返回所有满足 i != j 且 words[i] + words[j] 是回文字符串的有序下标对 [i, j]。
words 的长度位于 [1, 5000],每个字符串长度位于 [0, 300],字符只包含小写英文字母。空字符串是合法输入项;若另一个单词本身是回文,它与空字符串按两个拼接方向可能分别形成答案。[i,j] 与 [j,i] 是不同候选,结果顺序不限,但不能重复返回同一个下标对。
自建示例¶
反转单词与空字符串同时出现:
输入:words = ["abc", "cba", "x", ""]
输出:[[0,1], [1,0], [2,3], [3,2]]
解释:"abc"+"cba" 和反向拼接都为回文;"x" 本身是回文,所以它与空字符串的两个拼接顺序也都合法。
没有可组成回文的单词对:
输入:words = ["ab", "cd"]
输出:[]
解释:两个可能的拼接 "abcd" 和 "cdab" 都不是回文。
在每个拼接边界切开¶
考虑固定的 words[i],如果它与另一个单词拼接后是回文,那么两词的边界一定把这个回文划分成两段。对每个切分位置 split,记前缀为 prefix、后缀为 suffix:若 suffix 本身是回文,前缀的反转就可以放在它左侧;若 prefix 是回文,后缀的反转就可以放在它右侧。把所需的反转字符串放入哈希表查找,就不需要枚举另一个单词并实际拼接。
切分位置包含两端,因此能覆盖空字符串参与的情况;同一回文单词与空字符串可能在端点切分中被重复发现,结果用集合按下标对去重。只有找到的下标与 i 不同,才能满足题目的 i != j。
C++ 实现¶
class Solution {
bool isPalindrome(const std::string& word,
int left, int right) {
while (left < right) {
if (word[left++] != word[right--]) return false;
}
return true;
}
public:
std::vector<std::vector<int>> palindromePairs(
std::vector<std::string>& words) {
std::unordered_map<std::string, int> index;
for (int i = 0; i < static_cast<int>(words.size()); ++i) {
index[words[i]] = i;
}
std::set<std::pair<int, int>> uniquePairs;
for (int i = 0; i < static_cast<int>(words.size()); ++i) {
const std::string& word = words[i];
int length = static_cast<int>(word.size());
for (int split = 0; split <= length; ++split) {
if (isPalindrome(word, split, length - 1)) {
std::string need = word.substr(0, split);
std::reverse(need.begin(), need.end());
auto it = index.find(need);
if (it != index.end() && it->second != i) {
uniquePairs.insert({i, it->second});
}
}
if (isPalindrome(word, 0, split - 1)) {
std::string need = word.substr(split);
std::reverse(need.begin(), need.end());
auto it = index.find(need);
if (it != index.end() && it->second != i) {
uniquePairs.insert({it->second, i});
}
}
}
}
std::vector<std::vector<int>> result;
for (const auto& pair : uniquePairs) {
result.push_back({pair.first, pair.second});
}
return result;
}
};
代码分析¶
isPalindrome 对空区间也返回真,因此 split == 0 和 split == length 能自然处理空前缀或空后缀。两种方向分别对应回文边界的左右两侧,避免漏掉有序下标对;集合只去掉同一对被不同切分重复产生的情况。设单词总长度为 L、最大长度为 m,朴素边界检查总成本约为 O(Lm),哈希查找为平均常数,额外空间为反转临时串和结果集合。