力扣刷题4---回文序列

╰+哭是因爲堅強的太久メ 2023-02-18 12:52 40阅读 0赞

### 题目： ###

[力扣出处][Link 1]  
给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。  
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。  
回文串不一定是字典当中的单词。

示例1：

输入："tactcoa"
    输出：true（排列有"tacocat"、"atcocta"，等等）

### 思路详见代码： ###

class Solution { 
    public:
        bool canPermutePalindrome(string s) { 
            int num = 0;
            sort(s.begin(),s.end());  //排序用于比较
            for(int i = 0; i < s.size(); i++)
            { 
                if(s[i] == s[i+1])
                { 
                    num ++; 
                    i++;
                }    
            } 
            return num == s.size()/2;
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM3ODgwMA_size_16_color_FFFFFF_t_70]  
看到一个不错的做法分享给大家：

class Solution { 
    public:
        bool canPermutePalindrome(string s) { 
            vector<int> hash(256, 0);
            for (auto c : s) { 
                ++hash[c];
            }
            int cnt = 0;
            for (int i = 0; i < hash.size(); ++i) { 
                if (hash[i] % 2 == 1) ++cnt;
            }
            return cnt <= 1;
        }
    };
    
    作者：guohaoding
    链接：https://leetcode-cn.com/problems/palindrome-permutation-lcci/solution/mian-shi-ti-14-hui-wen-pai-lie-jian-dan-ha-xi-by-g/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[Link 1]: https://leetcode-cn.com/problems/palindrome-permutation-lcci/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM3ODgwMA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200617204513425.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM3ODgwMA==,size_16,color_FFFFFF,t_70