Palindrome Permutation

题目描述

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

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

解题方法

这一题写出几个例子就会发现规律，因为是Permutation，所以characters都可以任意排列。

• 首先看这个string的长度是奇数还是偶数
  • 如果是奇数，那必然是两边对称，中间有一个独特的character
  • 如果是偶数，就应该是两边对称
• 然后数每个character出现的次数
  • 如果长度是奇数，那么出了一个出现了奇数次的数外，其他的数都应该出现偶数次
  • 如果长度是偶数，那么所有数都应该出现偶数次

优化，注意点

• 为了便于判断奇偶，我将所有的出现次数都 % 2

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