leetcode 面试题01.04 回文字符串

题目：https://leetcode-cn.com/problems/palindrome-permutation-lcci/submissions/

思路一：哈希表法

分析：

根据回文字符串的特点只需要满足字符串中各个相同字母的个数为偶数或者只有一个奇数，其他都为偶数

步骤：

1、 定义一个哈希表，

2、统计各个字母的频率

3、定义一个数组，将频率放入数组内

4、统计数组里面奇数和偶数的个数

5、如果奇数个数为1，返回true；如果奇数个数为0，且偶数的个数不为0，返回true；否则就返回false

bool canPermutePalindrome(string s) {


        unordered_map<char,int>maap;
        for(char ch:s)
        {
            maap[ch]++;
        }
        
        vector<int>vec;


     for(auto kv : maap)
    {
     
         vec.push_back(kv.second);  
    }  
     int num=0;//计数个数
     int numt=0;


     for(int i=0;i<vec.size();i++)
     {
         if(vec[i]%2!=0)
           num++;
         else
           numt++;
     }
     if(num==1)
     {
       return true;
     }
     else if(num==0&&numt!=0)//考虑只有偶数个的情况
      return true;
      else
      return false;
 }

优化：
bool canPermutePalindrome(string s) {


        unordered_map<char,int>maap;
        for(char ch:s)
        {
            maap[ch]++;
        }
        
    int count=0;


     for(auto kv : maap)
    {
     
        int num=kv.second;
        if(num%2==1)
        {
            count++;
            if(count>1)
            return false;
        }
    }  
    return true;
}