【Python】文字列を並べ替えて回文にできるかどうかを判定するプログラム

文字列 s が与えられたとき、その文字を並べ替えて(アナグラムを作って)回文にできるかどうかを判定する問題を考えてみましょう。

たとえば、入力が s = "admma" の場合、「admma」の文字を組み替えると「madam」という回文を作ることができるため、出力は True になります。

解法のアプローチ

この問題は、次の手順で解くことができます。

• c := 文字列 s に含まれる各文字の出現回数を記録するマップ(カウンター)を作る
• count := 0 で初期化する
• c のすべての値(出現回数)について、以下を繰り返す
  • i が奇数の場合
    • count が 0 ならば、count を 1 増やして次の要素へ進む(continue)
    • そうでなければ False を返す
• 最後まで処理が終われば True を返す

なぜこのアルゴリズムが成り立つのか

回文とは、前から読んでも後ろから読んでも同じになる文字列です。回文では左右対称の位置に同じ文字が配置されるため、出現回数が奇数になる文字は最大でも1つ(中央に置く文字)しか存在できません。したがって、各文字の出現回数を数え、奇数回出現する文字が2つ以上見つかった時点で、どのように並べ替えても回文にできないと判断できます。

実装例

それでは、実際のコードを見て理解を深めましょう。

サンプルコード

from collections import Counter

class Solution:
    def solve(self, s):
        c = Counter(s)
        count = 0
        for i in c.values():
            if i % 2 != 0:
                if count == 0:
                    count += 1
                    continue
                return False
        return True

ob = Solution()
s = "admma"
print(ob.solve(s))

入力

"admma"

出力

True

コードの解説

collections.Counter を使うことで、文字ごとの出現回数を簡単に取得できます。あとは各文字の出現回数を走査し、奇数回出現する文字が最初に見つかった時点でフラグ(count)を立てます。2つ目の奇数回出現する文字が見つかった瞬間に False を返し、最後まで問題がなければ True を返します。

このアルゴリズムの計算量は O(n)(n は文字列の長さ)であり、非常に効率的に動作します。