266. Palindrome Permutation

https://leetcode.com/problems/palindrome-permutation/description/

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

For example,

"code" -> False, "aab" -> True, "carerac" -> True.

Thoughts

检验给定字符串能否通过重组变成回文。构成palindrome有且只有一个字符出现奇数次。统计奇偶用0/1记录就可以，出现奇数次1，偶数次置回0，利用次思想可以用位操作或hash set实现。

Code

class Solution {
public:
    bool canPermutePalindrome(string s) {
        vector<int> freqs(128, 0);
        for (const auto c : s) {
            freqs[c] = !freqs[c];
        }
        
        for (int i = 0, cnt = 0; i < 128; ++i) {
            if (freqs[i] != 0) {
                if (cnt > 0) return false;
                ++cnt;
            }
        }

        return true;
    }
};

class Solution {
    public boolean canPermutePalindrome(String s) {
        Set<Character> visited = new HashSet<>();
        for (char c : s.toCharArray()) {
            if (visited.contains(c)) {
                visited.remove(c);
            } else {
                visited.add(c);
            }
        }

        return visited.size() <= 1;
    }
}

Analysis

时间复杂度O(N).