python - 生成长度不超过 10^5 的字符串的回文字谜

Question

我已经尝试了以下方法，但是当我尝试 17 个字符的字符串时会花费太多时间。

string = input()

def permute(xs, low=0):
    if low + 1 >= len(xs):
        yield xs
    else:
        for p in permute(xs, low + 1):
            yield p        
        for i in range(low + 1, len(xs)):        
            xs[low], xs[i] = xs[i], xs[low]
            for p in permute(xs, low + 1):
                yield p        
            xs[low], xs[i] = xs[i], xs[low]
for p in permute(list(string)):
    mstr = "".join(p)
    if mstr == mstr[::-1]:
        print("YES")
        break

这实际上是我在hackerrank 上对“权力的游戏”挑战的解决方案。我怎样才能减少它的执行时间，让它运行得非常快，长度为 10^5 的字符串？

谢谢。

Answer 1

当然，尝试所有组合都不够快。有一种更简单的方法可以做到这一点。它基于以下观察：假设这是给定字符串count[c]中出现的次数。c那么答案是肯定的，当且仅当奇数值的字符数count小于或等于 1 时。这个观察给出了一个非常简单的O(N)解决方案。

这是一个伪代码：

count[c] = 0 for each character c that appears in the string
for i = 1...length(s):
    count[s[i]] += 1
with_odd_count = 0
for each c:
    if count[c] % 2 == 1:
        with_odd_count += 1
if with_odd_count <= 1:
    print("YES")
else:
    print("NO")