266. Palindrome Permutation

Link

Given a string, determine if a permutation of the string could form a palindrome.

Example 1:

Input: "code"
Output: false

Example 2:

Input: "aab"
Output: true

Example 3:

Input: "carerac"
Output: true

Hint:

1. Consider the palindromes of odd vs even length. What difference do you notice?

2. Count the frequency of each character.

3. If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?

Solution

如果是回文的話，只有下列兩種case:

1. 所有字元都要是偶數

2. 只有一個字元出現奇數，其他都是偶數。

  public boolean canPermutePalindrome(String s) {
        Set<Character> set = new HashSet<>();
        for(int i = 0; i < s.length(); i++){
            if(set.contains(s.charAt(i))) {
                set.remove(s.charAt(i));
            }
            else{
                set.add(s.charAt(i));
            }
        }
        if(set.isEmpty() || set.size() == 1){
            return true;
        }
        return false;
    }