README.md

面试题 01.04. 回文排列

English Version

题目描述

给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。

回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。

回文串不一定是字典当中的单词。

 

示例1：

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

 

解法

用哈希表存储每个字符出现的次数。若次数为奇数的字符超过 1 个，则不是回文排列。

Python3

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        if s is None or len(s) < 2:
            return True
        cache = {}
        for ch in s:
            cache[ch] = 1 if cache.get(ch) is None else cache[ch] + 1
        cnt = 0
        for k, v in cache.items():
            if (v & 1) == 1:
                cnt += 1
            if cnt > 1:
                return False
        return cnt <= 1

Java

class Solution {
    public boolean canPermutePalindrome(String s) {
        if (s == null || s.length() < 2) {
            return true;
        }
        char[] chars = s.toCharArray();
        Map<Character, Integer> counter = new HashMap<>();
        for (char ch : chars) {
            counter.put(ch, counter.get(ch) == null ? 1 : counter.get(ch) + 1);
        }
        int cnt = 0;
        for (Map.Entry<Character, Integer> entry : counter.entrySet()) {
            if ((entry.getValue() & 1) == 1) {
                ++cnt;
            }
            if (cnt > 1) {
                return false;
            }
        }
        return cnt <= 1;
    }
}

...