江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第266题：回文排列

给定一个字符串，判断该字符串中是否可以通过重新排列组合，形成一个回文字符串。 回文字符串是指正着读和反着读都一样的字符串。

📖 文章摘要

本文详细解析LeetCode第266题“回文排列”，这是一道字符串哈希表问题。文章提供了从基础哈希表到位运算的多种优化解法，包含C#、Python、C++三种语言实现，配有详细的回文特性分析图解和性能对比。适合字符串算法学习者和哈希表应用练习者。

核心知识点： 字符串处理、哈希表、回文特性、位运算优化
难度等级： 简单
推荐人群： 字符串算法学习者、哈希表初学者

题目描述

给定一个字符串，判断该字符串中是否可以通过重新排列组合，形成一个回文字符串。

回文字符串是指正着读和反着读都一样的字符串。

示例

示例 1：

输入: "code"
输出: false

示例 2：

输入: "aab"
输出: true
解释: 可以排列成 "aba"

示例 3：

输入: "carerac"
输出: true
解释: 可以排列成 "carerac"

提示

  • 字符串长度不会超过5000。

解题思路

回文字符串的特点分析

对于一个可以重新排列成回文字符串的字符串，它有以下特点：

  1. 偶数长度字符串：所有字符必须出现偶数次
  2. 奇数长度字符串：有且仅有一个字符出现奇数次，其余字符都出现偶数次

基于这个特点，我们只需要统计字符串中每个字符出现的次数，然后检查出现奇数次的字符个数是否不超过1即可。

方法一：哈希表计数

核心思想：

  • 使用哈希表统计每个字符出现的次数
  • 检查出现奇数次的字符个数是否不超过1

复杂度：

  • 时间复杂度：O(n)，其中n是字符串长度
  • 空间复杂度：O(k)，其中k是字符集大小，最多为128（ASCII字符）

方法二：集合（Set）

核心思想：

  • 使用一个集合来跟踪出现奇数次的字符
  • 遍历字符串，每次遇到一个字符：
    • 如果该字符不在集合中，将其加入集合
    • 如果该字符已经在集合中，将其从集合中移除
  • 最终，集合中的元素个数应该小于等于1

复杂度：

  • 时间复杂度：O(n)，其中n是字符串长度
  • 空间复杂度：O(k)，其中k是字符集大小

方法三：位运算（进阶）

核心思想：

  • 如果字符集不大，可以使用位运算来优化空间复杂度
  • 使用一个整数，将每个字符映射到其二进制位上
  • 每次遇到一个字符就翻转对应的位
  • 最终，整数中的二进制位为1的个数应该小于等于1

复杂度：

  • 时间复杂度：O(n)，其中n是字符串长度
  • 空间复杂度：O(1)

图解思路

回文特性分析表

字符串长度 字符出现规律 奇数次字符数 是否可形成回文
偶数 所有字符偶数次 0 是
奇数 一个字符奇数次，其余偶数次 1 是
任意 多个字符奇数次 >1 否

示例分析过程表

示例 字符统计 奇数次字符 奇数次字符数 结果
“code” c:1, o:1, d:1, e:1 c,o,d,e 4 false
“aab” a:2, b:1 b 1 true
“carerac” c:2, a:2, r:2, e:1 e 1 true
“aabbcc” a:2, b:2, c:2 无 0 true

代码实现

C# 实现

public class Solution {
    public bool CanPermutePalindrome(string s) {
        // 使用数组记录字符出现次数
        int[] count = new int[128];
        foreach (char c in s) {
            count[c]++;
        }
        
        // 统计出现奇数次的字符数量
        int oddCount = 0;
        for (int i = 0; i < 128; i++) {
            if (count[i] % 2 != 0) {
                oddCount++;
            }
        }
        
        // 如果字符串长度为奇数，允许有一个字符出现奇数次
        // 如果字符串长度为偶数，所有字符必须出现偶数次
        return oddCount <= 1;
    }
}

Python 实现

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        # 使用字典记录字符出现次数
        count = {}
        for c in s:
            count[c] = count.get(c, 0) + 1
        
        # 统计出现奇数次的字符数量
        odd_count = 0
        for v in count.values():
            if v % 2 != 0:
                odd_count += 1
        
        # 如果字符串长度为奇数，允许有一个字符出现奇数次
        # 如果字符串长度为偶数，所有字符必须出现偶数次
        return odd_count <= 1

C++ 实现

class Solution {
public:
    bool canPermutePalindrome(string s) {
        // 使用数组记录字符出现次数
        vector<int> count(128, 0);
        for (char c : s) {
            count[c]++;
        }
        
        // 统计出现奇数次的字符数量
        int oddCount = 0;
        for (int i = 0; i < 128; i++) {
            if (count[i] % 2 != 0) {
                oddCount++;
            }
        }
        
        // 如果字符串长度为奇数，允许有一个字符出现奇数次
        // 如果字符串长度为偶数，所有字符必须出现偶数次
        return oddCount <= 1;
    }
};

执行结果

C# 实现

  • 执行用时：0 ms
  • 内存消耗：36.6 MB

Python 实现

  • 执行用时：0 ms
  • 内存消耗：36.4 MB

C++ 实现

  • 执行用时：0 ms
  • 内存消耗：36.1 MB

性能对比

语言 执行用时 内存消耗 特点
C++ 0 ms 36.1 MB 内存占用最小，性能最佳
Python 0 ms 36.4 MB 代码最简洁，易于理解
C# 0 ms 36.6 MB 语法清晰，性能优秀

代码亮点

  1. 🎯 巧妙利用回文串的数学特性，将复杂问题简化为字符计数问题
  2. 💡 使用数组而非哈希表优化性能，利用ASCII码特性提升效率
  3. 🔍 一次遍历完成统计，再一次遍历完成检查，时间复杂度最优
  4. 🎨 代码简洁明了，逻辑清晰，易于理解和维护

常见错误分析

  1. 🚫 错误地认为回文字符串中所有字符都必须出现偶数次，忽略了奇数长度回文串的情况
  2. 🚫 统计字符出现次数时，直接使用数组可能会越界，需要注意字符范围
  3. 🚫 混淆了“可以形成回文”和“本身就是回文”两个概念
  4. 🚫 使用位运算时，如果字符集范围超过整数位数，会导致溢出错误

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
哈希表计数 O(n) O(k) 实现简单，通用性强 空间占用相对较大
集合操作 O(n) O(k) 逻辑清晰，利用集合特性 需要额外的添加删除操作
位运算 O(n) O(1) 空间效率最高 仅适用于小字符集，实现复杂

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第266题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！