给定一个字符串，确定它的任何排列是否是回文

Question

我正在尝试确定任何字符串是否为回文。例如，carrace 应该 return 为真，因为它可以重新排列形成 racecar，这是一个回文。 daily 应该 return false 因为没有可以形成回文的重排。我该如何解决这个问题？

代码：

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

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

Answer 1

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 2

一个字符串可以置换为回文当且仅当最多一个字符出现奇数次 .

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 的任何倍数都是偶数）。唯一的例外是奇数长度字符串的中间字符，这个字符本身是 'paired'。所以最多有一个字符出现奇数次。

任何最多有一个字符出现奇数次的字符串都可以置换为回文：
我们通过以下方式展示回文 p 的构造。如果某个字符出现奇数次，则将其添加到 p。对于任何出现偶数次的字符，将其一分为二，一部分添加到 p 的开头，一部分添加到 p 的结尾。这导致回文。

例如：aabbbbccd
p = d
p = ada
p = bbadabb
p = cbbadabbc

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;
}

给定一个字符串，确定它的任何排列是否是回文

Given a string, determine whether any permutation of it is a palindrome

python

string

palindrome