leetcode解题: Palindrome Permutation (266)

发表于 | 分类于

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

For example,
“code” -> False, “aab” -> True, “carerac” -> True.

解法1：DP with O(N) time, N = number of characters

Palindrome分为even和odd两种情况，在even的时候，一定是每一个字母都出现偶数次。在odd的时候，有且仅有一个字母可出现奇数次。那么就可以统计每一个字母出现的次数，如果出现奇数次的字母的个数大于1，那么一定不能组成一个Palindrome，反之则可以。统计的时候需要一个HashMap来记录每一个字母的个数。
C++

lang: cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool canPermutePalindrome(string s) {
        map<char, int> hmap;
        for (int i = 0; i < s.length(); i++) {
            if (hmap.count(s[i]) == 0) {
                // not exist
                hmap.insert(std::pair<char, int>(s[i], 1));
            } else {
                hmap[s[i]]++;
            }
        }
        // Iterate over map keys
        map<char, int>::iterator iter = hmap.begin();
        map<char, int>::iterator iter_end = hmap.end();
        int odd = 0;
        while (iter != iter_end) {
            if (iter->second % 2 != 0) {
                odd++;
            }
            ++iter;
        }
        return odd < 2;
    }
};

Java

lang: java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public boolean canPermutePalindrome(String s) {
        if (s == null || s.length() == 0) {
            return false;
        }
        int size = s.length();
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < size; i++) {
            if (map.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
            } else {
                map.put(s.charAt(i), 1);
            }
        }
        // Check for odd number
        int odd = 0;
        for (Character ch : map.keySet()) {
            if (map.get(ch) % 2 != 0) {
                odd++;
            }
        }
        return odd < 2;
    }
}