01.04、回文排序

01.04、[简单] 回文排序1、题目描述给定一个字符串编写一个函数判定其是否为某个回文串的排列之一。回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。回文串不一定是字典当中的单词。2、解题思路回文串的特点一个回文串在字符出现次数上有特定的规律在回文串中所有字符的出现次数都必须是偶数除非字符串的长度是奇数那么只有一个字符可以出现奇数次其它所有字符都必须出现偶数次。例如racecar是一个回文串因为r,a,c都是偶数次出现且字符e出现了一次奇数次。统计字符出现次数我们可以通过一个计数器数组来记录每个字符出现的次数。检查奇数次字符的数量如果有超过一个字符的出现次数是奇数那么字符串无法重新排列成回文串。否则字符串可以重新排列成一个回文串。3、代码实现class Solution { public: bool canPermutePalindrome(string s) { // 创建一个大小为 128 的数组来记录每个字符的出现次数 int hash[128] {0}; for (const auto ch : s) { hash[ch]; // 统计每个字符的出现次数 } int ans 0; // 用于记录出现次数为奇数的字符数量 for (int i 0; i 128; i) { if (hash[i] % 2) { ans; // 如果出现次数是奇数增加计数 } } // 如果出现次数为奇数的字符数量不超过 1说明可以排列成回文串 return ans 1; } };4、代码详解初始化一个大小为 128 的整型数组hash用于记录 ASCII 字符的出现次数。ASCII 码表的字符范围是 0-127因此我们使用 128 大小的数组。遍历字符串s中的每个字符并增加对应位置的计数。hash[ch]将字符ch对应的计数增加 1。初始化一个变量ans用于记录字符出现次数为奇数的数量。遍历hash数组检查每个字符的出现次数。如果出现次数是奇数则将ans增加 1。检查ans的值。如果出现次数为奇数的字符数量不超过 1那么字符串可以排列成回文串返回true否则返回false。5、总结通过统计每个字符的出现次数并检查出现次数为奇数的字符数量我们可以有效地判断一个字符串是否能够通过重新排列字符形成一个回文串。这种方法的时间复杂度为 O(n)其中 n 是字符串的长度空间复杂度为 O(1)因为hash数组的大小是固定的。