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;
}