给定一个字符串，判断该字符串的任何排列是否为回文

Question

我试图确定是否有任何字符串是回文。例如，carrace应该返回true，因为它可以重新排列成racecar，这是一个回文。Daily应该返回false，因为没有可以形成回文的重排。如何解决这个问题?

代码:

string = 'racecar'
if string[::-1] == string:
print('palindrome')

以上代码适用于单个字符串，不适用

排列

Answer 1

字符串可以被排列成回文当且仅当最多有一个字符出现奇数次.

from collections import Counter
def permute_palindrome(s):
return sum(1 for i in Counter(s).values() if i%2) <= 1
assert permute_palindrome('carrace')
assert not permute_palindrome('daily')

详细解释:

任何回文最多有一个字符出现且出现次数为奇数:
考虑任何回文aabbcccbbaa
请注意，根据回文的定义，左侧的任何字符都与右侧匹配，因此它与该字符形成一对。成对计算字符总是会得到一个偶数(2的任何倍数都是偶数)。唯一的例外是奇数长度字符串的中间字符，该字符与自身"配对"。因此，最多有一个字符出现奇数次。

任何最多有一个字符出现奇数次的字符串都可以排列成回文:
我们用下面的方式展示回文p的构造。如果有一个字符出现奇数次，将其添加到p中。对于任何出现偶数次的字符，将其分成两部分，并将一部分添加到p的开头，另一部分添加到p的结尾。这将得到一个回文。

ex: aabbbbccd
p = d
p = ada
p = bbadabbc
p = bbadabbc

Answer 2

from itertools import permutations
def palindrome(s: str) -> bool:
return ''.join(reversed(s)) == s
def permutated_palindrome(s: str) ->:
return any(map(palindrome,
map(''.join, permutations(s))
))

Answer 3

Java精简版

boolean isPermutationPalindrome(String s){
Set<Character> charSet = new HashSet<>();
for ( char c : s.toCharArray() ) {
if (!charSet.contains(c))
charSet.add(c);
else
charSet.remove(c);
}
return charSet.size() <= 1;
}