力扣---面试题 01.04. 回文排列

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

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

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

示例1：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindrome-permutation-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目的意思，实际上是说，把一个字符串中的所有字符进行各种排列后，是否会出现一个回文字符。

判断的方法也很简单，根据回文字符的特点，可以很容易就联想到一个回文字符中不同字符的数量最多只有一种是奇数，其他都必定是偶数。

由于题目没有给出字符集，无法判断是否包含其他符号甚至是汉字等。此时可以利用哈希表来解决。

哈希表可以用Map来保存所有字符的数量，最后再遍历即可，优化后可以利用Set，由于我们只需要判断数量是否是偶数，所以可以在Set中含有相同元素时，将Set中的该元素移除。最后判断Set的长度是否小于等于1即可。

Map：

class Solution {
    public boolean canPermutePalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        // 判断是否包含多个数量为奇数的字符
        boolean ju = false;
        // 只需要value
        for (Integer value : map.values()) {
            if (value % 2 != 0) {
                if (ju) {
                    return false;
                } else {
                    ju = true;
                }
            }
        }
        return true;
    }
}

 Set：

class Solution {
    public boolean canPermutePalindrome(String s) {
        Set<Character> set = new HashSet<>();
        for (char c : s.toCharArray()) {
            if (set.contains(c)) {
                // 遇到已经含有后移除，确保set中的字符都是出现次数为奇数的字符。
                set.remove(c);
            } else {
                set.add(c);
            }
        }
        return set.size() <= 1;
    }
}