Palindrome Permutation

题目描述

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

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

解题方法

这一题根据提示应该按照palindrome的特征才判断，就可以达到时间O(n)的复杂度。

• 用一个hashtable来记录每个character出现的次数
• 如果string长度是偶数，那么每个char出现的次数都必须是偶数
• 如果string长度是奇数，那么必须有且仅有一个字符出现的次数是奇数

Solution

class Solution(object):
    def canPermutePalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if len(s) == 0:
            return True

        dic = {}
        for i in range(len(s)):
            if s[i] not in dic:
                dic[s[i]] = 1
            else:
                dic[s[i]] += 1
                dic[s[i]] %= 2

        foundOdd = 0
        for key in dic:
            if dic[key] == 1:
                foundOdd += 1

        if len(s) % 2 == 0:
            if foundOdd != 0:
                return False
            else:
                return True
        else:
            if foundOdd == 1:
                return True
            else:
                return False

Reference