Article / 文章
LeetCode 第336题：回文对
给定一组 互不相同 的单词， 找出所有 不同 的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。
📖 文章摘要
本文详细解析LeetCode第336题“回文对”，这是一道困难难度的字符串和哈希表问题。文章提供了基于哈希表和字符串处理的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升字符串处理和哈希表应用能力的程序员。
核心知识点： 字符串、哈希表、回文串、前缀后缀处理
难度等级： 困难
推荐人群： 具有基础数据结构知识，想要提升字符串算法能力的程序员
题目描述
给定一组 互不相同 的单词， 找出所有 不同 的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。
示例
示例 1：
输入：words = ["abcd","dcba","lls","s","sssll"]
输出：[[0,1],[1,0],[3,2],[2,4]]
解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]示例 2：
输入：words = ["bat","tab","cat"]
输出：[[0,1],[1,0]]
解释：可拼接成的回文串为 ["battab","tabbat"]示例 3：
输入：words = ["a",""]
输出：[[0,1],[1,0]]提示
- 1 <= words.length <= 5000
- 0 <= words[i].length <= 300
- words[i] 由小写英文字母组成
- words 中的所有字符串互不相同
解题思路
方法：哈希表 + 字符串处理
使用哈希表存储单词的反转形式，并通过分割单词来查找可能的回文对。
关键点：
- 使用哈希表存储单词和索引
- 处理空字符串的特殊情况
- 分割单词查找回文对
- 避免重复计算
具体步骤：
- 构建哈希表存储单词和索引
- 遍历每个单词，分割为左右两部分
- 检查左部分是否回文，右部分是否存在匹配
- 检查右部分是否回文，左部分是否存在匹配
- 处理空字符串的特殊情况
时间复杂度：O(n * k^2)，其中n是单词数量，k是单词的最大长度 空间复杂度：O(n * k)
图解思路
算法流程分析表
| 步骤 | 操作 | 状态 | 说明 |
|---|---|---|---|
| 初始化 | 构建哈希表 | 存储单词和索引 | 便于快速查找 |
| 分割单词 | 左右部分 | 检查回文可能 | 找到潜在匹配 |
| 查找匹配 | 在哈希表中查找 | 寻找回文对 | 记录结果 |
| 特殊处理 | 空字符串 | 额外检查 | 处理边界情况 |
示例分析
words = ["abcd","dcba","lls","s","sssll"]
1. 构建哈希表：
"abcd" -> 0
"dcba" -> 1
"lls" -> 2
"s" -> 3
"sssll" -> 4
2. 分析 "abcd"：
- 完整反转 "dcba" 存在
- 找到回文对 [0,1]
3. 分析 "lls"：
- 分割为 "l|ls"
- "s" 存在且 "l" 是回文
- 找到回文对 [3,2]代码实现
C# 实现
public class Solution {
public IList<IList<int>> PalindromePairs(string[] words) {
var result = new List<IList<int>>();
var dict = new Dictionary<string, int>();
// 构建哈希表
for (int i = 0; i < words.Length; i++) {
dict[words[i]] = i;
}
// 检查每个单词
for (int i = 0; i < words.Length; i++) {
string word = words[i];
int len = word.Length;
// 处理空字符串的特殊情况
if (len == 0) {
for (int j = 0; j < words.Length; j++) {
if (i != j && IsPalindrome(words[j], 0, words[j].Length - 1)) {
result.Add(new List<int> { i, j });
result.Add(new List<int> { j, i });
}
}
continue;
}
// 检查单词的反转是否存在
string reversed = new string(word.Reverse().ToArray());
if (dict.ContainsKey(reversed) && dict[reversed] != i) {
result.Add(new List<int> { i, dict[reversed] });
}
// 分割单词检查可能的回文对
for (int j = 1; j < len; j++) {
// 检查左半部分
if (IsPalindrome(word, 0, j - 1)) {
string rightReversed = new string(word.Substring(j).Reverse().ToArray());
if (dict.ContainsKey(rightReversed)) {
result.Add(new List<int> { dict[rightReversed], i });
}
}
// 检查右半部分
if (IsPalindrome(word, j, len - 1)) {
string leftReversed = new string(word.Substring(0, j).Reverse().ToArray());
if (dict.ContainsKey(leftReversed)) {
result.Add(new List<int> { i, dict[leftReversed] });
}
}
}
}
return result;
}
private bool IsPalindrome(string word, int left, int right) {
while (left < right) {
if (word[left++] != word[right--]) return false;
}
return true;
}
}Python 实现
class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
def is_palindrome(word: str, left: int, right: int) -> bool:
while left < right:
if word[left] != word[right]:
return False
left += 1
right -= 1
return True
word_dict = {word: i for i, word in enumerate(words)}
result = []
for i, word in enumerate(words):
length = len(word)
# 处理空字符串
if length == 0:
for j, other in enumerate(words):
if i != j and is_palindrome(other, 0, len(other) - 1):
result.append([i, j])
result.append([j, i])
continue
# 检查完整反转
reversed_word = word[::-1]
if reversed_word in word_dict and word_dict[reversed_word] != i:
result.append([i, word_dict[reversed_word]])
# 分割检查
for j in range(1, length):
# 检查左半部分
if is_palindrome(word, 0, j - 1):
right_reversed = word[j:][::-1]
if right_reversed in word_dict:
result.append([word_dict[right_reversed], i])
# 检查右半部分
if is_palindrome(word, j, length - 1):
left_reversed = word[:j][::-1]
if left_reversed in word_dict:
result.append([i, word_dict[left_reversed]])
return resultC++ 实现
class Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
vector<vector<int>> result;
unordered_map<string, int> dict;
// 构建哈希表
for (int i = 0; i < words.size(); i++) {
dict[words[i]] = i;
}
// 检查每个单词
for (int i = 0; i < words.size(); i++) {
string& word = words[i];
int len = word.length();
// 处理空字符串
if (len == 0) {
for (int j = 0; j < words.size(); j++) {
if (i != j && isPalindrome(words[j], 0, words[j].length() - 1)) {
result.push_back({i, j});
result.push_back({j, i});
}
}
continue;
}
// 检查完整反转
string reversed = word;
reverse(reversed.begin(), reversed.end());
if (dict.count(reversed) && dict[reversed] != i) {
result.push_back({i, dict[reversed]});
}
// 分割检查
for (int j = 1; j < len; j++) {
// 检查左半部分
if (isPalindrome(word, 0, j - 1)) {
string rightReversed = word.substr(j);
reverse(rightReversed.begin(), rightReversed.end());
if (dict.count(rightReversed)) {
result.push_back({dict[rightReversed], i});
}
}
// 检查右半部分
if (isPalindrome(word, j, len - 1)) {
string leftReversed = word.substr(0, j);
reverse(leftReversed.begin(), leftReversed.end());
if (dict.count(leftReversed)) {
result.push_back({i, dict[leftReversed]});
}
}
}
}
return result;
}
private:
bool isPalindrome(const string& word, int left, int right) {
while (left < right) {
if (word[left++] != word[right--]) return false;
}
return true;
}
};执行结果
C# 实现
- 执行用时：396 ms
- 内存消耗：52.8 MB
Python 实现
- 执行用时：328 ms
- 内存消耗：26.4 MB
C++ 实现
- 执行用时：92 ms
- 内存消耗：42.1 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 396 ms | 52.8 MB | 代码结构清晰 |
| Python | 328 ms | 26.4 MB | 实现最简洁 |
| C++ | 92 ms | 42.1 MB | 性能最优 |
代码亮点
- 🎯 高效的哈希表应用
- 💡 巧妙的字符串分割策略
- 🔍 完整的边界条件处理
- 🎨 清晰的代码结构
常见错误分析
- 🚫 忽略空字符串的处理
- 🚫 未考虑重复索引
- 🚫 回文判断错误
- 🚫 字符串分割不当
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 哈希表 | O(n * k^2) | O(n * k) | 实现简单 | 空间消耗大 |
| 字典树 | O(n * k^2) | O(n * k) | 查找效率高 | 实现复杂 |
相关题目
- LeetCode 5. 最长回文子串 - 中等
- LeetCode 214. 最短回文串 - 困难
- LeetCode 409. 最长回文串 - 简单
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第336题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！