1.4 Palindrome Permutation

Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words.
EXAMPLE
Input: Tact Coa
Output: true (permutations: "taco cat". "atco cta". etc.)

Hint

• You do not have to — and should not — generate all permutations. This would be very inefficient.
• What characteristics would a string that is a permutation of a palindrome have?
• Have you tried a hash table? You should be able to get this down to O(N) time.
• Can you reduce the space usage by using a bit vector?

Solution

本题要求判断给出的字符串是否为一个回文字符串的一种全排列，也相当于是要我们求出给定的字符串经过排列后是否为一个回文字符串，条件中提到了排列letters，因此可以忽略非字母字符。对于某个回文字符串，只可能有两种情况：1.字符串长度为偶数，那么每个字母均出现偶数次；2.字符串长度为奇数，那么有且仅有一个字母出现奇数次。
首先来看一种基于HashSet的实现。基于上面的两条性质，遍历字符串中每个字母，如果set中不存在，则加入该字符，如果已经存在，则删除该字符。最终set为空或者只有一个字符时说明为回文字符串。

public boolean isPalindromePermutation(String str) {
    if (str == null || str.isEmpty()) return false;
    Set<Character> set = new HashSet<>();
    for (char ch : str.toCharArray()) {
        if (Character.isLetter(ch)) {
            char lowCase = Character.toLowCase(ch);
            if (!set.add(lowCase)) set.remove(lowCase);
        }
    }
    return set.isEmpty() || set.size() == 1;
}

还有一种基于位操作的实现，设置一个int型变量检查器，若字符对应位置为0则置为1，否则置为0。模拟上面方法中set的add与remove操作。最后判断检查器变量中1的个数。

public boolean isPalindromePermutation(String str) {
    if (str == null || str.isEmpty()) return false;
    int monitor = 0;
    for (char ch : str.toCharArray()) {
        if (Character.isLetter(ch)) {
            int pos = Character.toLowerCase(ch) - 'a';
            int mask = 1 << pos;
            if ((monitor & mask) == 0) {
                monitor |= mask; // 若字符未出现过，置为1
            } else {
                monitor &= ~mask; // 若字符出现过，置为0
            }
        }
    }
    return (monitor & (monitor - 1)) == 0;
}