leetcode 链接：回文排列

题目

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

示例：

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

解答 & 代码

思想：如果是某个回文串的重新排列，那么就要求每个字符出现的次数都为偶数，或者只有一个字符出现奇数次

  • 使用哈希表，记录字符串中每个字符出现的次数
  • 遍历哈希表，统计出现次数为奇数的字符个数
    • 若出现次数为奇数的字符个数大于 1，则返回 false
    • 否则，返回 true ```cpp

      include

class Solution { public: bool canPermutePalindrome(string s) { //使用哈希表，记录字符串中每个字符出现的次数 unordered_map ch_cnt_map; for(int i = 0; i < s.size(); ++i) { if(ch_cnt_map.find(s[i]) == ch_cnt_map.end()) ch_cnt_map.insert(make_pair(s[i], 1)); else ++ch_cnt_map[s[i]]; }

    //遍历哈希表，统计出现次数为奇数的字符个数
    int odd_cnt = 0;
    for(auto it = ch_cnt_map.begin(); it != ch_cnt_map.end(); ++it)
    {
        if(it->second % 2 == 1)
            ++odd_cnt;
    }
    if(odd_cnt > 1)
        return false;
    else
        return true;
}

};

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户 内存消耗：6.1 MB, 在所有 C++ 提交中击败了 73.42% 的用户 ```