0

以下を試してみましたが、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 の文字列を高速に実行するにはどうすればよいですか?

ありがとう。

4

1 に答える 1

1

Trying all combination cannot be fast enough, of course. There is a much simpler way to do it. It is based on the following observation: let's assume that count[c] is the number of occurrences of c in the given string. Then the answer is YES if and only if the number of characters with odd value of count is less than or equal to 1. This observation gives a very simple O(N) solution.

Here is a pseudo code:

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")
于 2014-11-07T14:24:48.707 に答える