题目
给定一个字符串,编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词。
示例1:
输入:"tactcoa" 输出:true(排列有"tacocat"、"atcocta",等等)
解题
方法一:哈希表
由于要可以排序成回文串,那么最多只能有一个字符的数量为奇数(放在最中间),其他均要为偶数
假设有n个字符,以下两种情况是可行的
- n个偶数
- n-1个偶数,1个奇数
因此只要判断 字符数量为奇数出现超过1次的,就不能排列为回文串。
class Solution { public: bool canPermutePalindrome(string s) { unordered_map<char,int> map; for(char c:s) map[c]++; int oddNum=0; for(pair<char,int> kv:map){ if(kv.second%2==1){ oddNum++; if(oddNum>1) return false; } } return true; } };