Cracking the Coding Interview-1.4

第六版Cracking the Coding Interview题目1.4，题目如下：

Palindrome Permutation: Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearreangement of letters. The palindrome does not need to be limited to just dictionary words.

EXAMPLE
Input: Tact Coa
Output: True (permutations: "taco cat". "atco cta". etc.)

这题需要判断一个字符串是不是回文的一种置换。可以想到若需判断所有置换复杂度将会非常高，可以考虑到回文的特性，即字符串中每个字均出现偶数次（当字符串长度为偶数时），或者一个字符出现奇数次其他所有字符均出现偶数次（当字符串长度为奇数时）。从例子中看出，我们并不需要考虑空格(书中给出的答案中也不考虑其他特殊符号)，Python实现如下：

from collections import Counter
def isPermutationOfPalindrome(str_):
    counter = Counter(str_)
    oddCount=0
    for c in counter:
        if not c.isalnum(): # assuming that .isalnum() is O(1) for 1 character
            continue
        if counter[c] % 2 == 1:
            oddCount += 1
        if oddCount > 1:
            return False
    return True

为了更简洁也可以写成如下一行代码，但这种写法运行速度并不一定会更快。

# Python 2.7
from collections import Counter
def isPermutationOfPalindrome(str_):
    return sum(map(lambda x: x % 2, Counter(filter(lambda c: c.isalnum(), str_)).values())) < 2

在手机上阅读或分享本文请扫描以下二维码：

Cracking the Coding Interview-1.4

Comments