如何检查字符串的排列是否是回文

Question

我是 python 新手，我试图检查字符串的任何排列是否是回文。这是我的代码：

def isPal(s):
    a = set()
    for i in s:
        if i in a:
            a.remove(i)
        else:
            if (i != '\n') or (i != ' '):
                a.add(i)
    if len(a) <= 1:
        print(s + ' is a palindrome permutation\n')
    else:
        print(s + ' is not a palindrome permutation\n')
     print(a)

我遇到的问题是我不希望我的集合包含空格或字符串中的任何标点符号。有没有办法只检查字母？例如，字符串“Mr. owl ate my Metal worm”在检查是否为回文时不应使用句点或空格。

Answer 1

您当然可以检查所有排列，但还有一种更有效的方法。

请注意，为了使字符串成为回文，每个字母都围绕字符串的中心进行镜像。这意味着如果最多有一个字母的计数为奇数，则一组字母可以形成回文。

以下是实现此方法的方法：

第一步是将字符串转换为小写并删除非字母字符（如空格和标点符号）。我们可以通过使用列表理解来迭代字符串中的每个字符并仅保留那些str.isalpha()return 的字符来做到这一点True。

myString = "Mr. owl ate my Metal worm"
alpha_chars_only = [x for x in myString.lower() if x.isalpha()]
print(alpha_chars_only)
#['m', 'r', 'o', 'w', 'l', 'a', 't', 'e', 'm', 'y', 'm', 'e', 't', 'a', 'l', 'w', 'o', 'r', 'm']

接下来数一下每个字母。您可以collections.Counter为此使用：

from collections import Counter 
counts = Counter(alpha_chars_only)
print(counts)
#Counter({'m': 4, 'a': 2, 'e': 2, 'l': 2, 'o': 2, 'r': 2, 't': 2, 'w': 2, 'y': 1})

最后计算奇数个字母的数量。如果计数为0或1，则回文数一定是可能的。

number_of_odd = sum(1 for letter, cnt in counts.items() if cnt%2)
print(number_of_odd)
#1

将所有这些放在一起，您可以创建一个函数：

def any_palindrome(myString):
    alpha_chars_only = [x for x in myString.lower() if x.isalpha()]
    counts = Counter(alpha_chars_only)
    number_of_odd = sum(1 for letter, cnt in counts.items() if cnt%2)
    return number_of_odd <= 1

print(any_palindrome(mystring))
#True