检查字符串，看看它是否是它的任何排列的回文

Question

我已经创建了一个函数，可以成功地实现这一点（我非常确定），但我担心它的部分效率。我有两个嵌套的for循环，我认为这使得这个算法的最坏情况是O（n^2）。我有什么办法可以改进吗？在

def palindrome(string):
    s = [c.replace(' ', '') for c in string]
    merged = "".join(s)
    srt = sorted(merged)
    dic = {}
    singles = 0

    for i in srt:
        if i not in dic:
            dic[i] = 1
        else:
            # Worried about this second loop having to run for every i in srt
            for key, value in dic.items():
                if key == i:
                    dic[key] = 2 
    for key, value in dic.items():
        if value == 1:
            singles += 1
    if singles > 1:
        return False
    else:
        return True

Answer 1

如果某个字符出现三次，以上代码将失败。尝试abcabccddd

稍作修改以解决问题：

def checkPalindromPermutation(word):
    values = collections.Counter(word).values()
    if sum((v % 2) for v in values) > 1 or any(v > 2 for v in values):
        return False
    return True

Answer 2

你需要的是找出是否最多有一个“单个”字母（其他字母是成对的）。因此，我们用collections.Counter对字母进行计数，并确保其中只有0或1具有奇数：

from collections import Counter


def has_palindrome(string):
    return sum(v % 2 for v in Counter(string).values()) <= 1

print(has_palindrome('abcabcc'))  # True
print(has_palindrome('abc'))  # False

Answer 3

它测试字符串中字母的任何排列是否可以是回文。在

我建议：

from collections import Counter

def palindrome(string):
    s = string.replace(' ', '')
    return not sum(v % 2 == 1 for k,v in Counter(string)) > 1

此检查奇数字符出现计数的总和不大于1。在