Pythonで回文を判定する方法：文字列が回文かどうかを確認する

回文とは？

回文（パリンドローム）とは、左から読んでも右から読んでも同じになる文字列のことです。言い換えると、文字列を逆順に並べ替えたときに元の文字列と完全に一致するものを指します。

例えば、「civic」や「madam」は回文です。

一方、「cat」は回文ではありません。逆順にすると「tac」となり、元の文字列「cat」と一致しないためです。

この記事では、入力された文字列が回文かどうかを判定するプログラムの書き方を、2つの方法で解説します。

方法1：文字列の逆順を求めて比較する

• この方法のポイントは、文字列の逆順を作成することです。

• 逆順の取得にはさまざまな方法がありますが、ここでは最もシンプルなスライスを使用します。組み込みの ''.join(reversed()) を使うことも可能ですが、ここでは簡潔なスライス方式を採用します。

• 作成した逆順の文字列を、元の文字列と比較します。

• 両者が一致すれば True を返し、一致しなければ False を返します。

コード例

def isPalindrome(s):
    rev = s[::-1]
    if rev == s:
        return True
    return False

print("Enter a string")
st = input()
print(isPalindrome(st))

実行結果

Enter a string
madam
True

s[::-1] というスライス記法により、文字列全体を1ステップずつ逆方向に走査した新しい文字列が生成されます。この方法はコードが短く直感的なので、Python初心者にもおすすめです。

方法2：逆順を作らずに判定する（2ポインタ法）

次の方法では、文字列の先頭と末尾の文字を順番に比較していき、一致しない文字が見つかった時点で処理を終了するという考え方を使います。

文字列 "madam" の場合

• 最初と最後の文字（m と m）を比較して一致。次に2番目と後ろから2番目の文字（a と a）も一致します。

• 最後に残るのは中央の1文字だけで、これは必ず自分自身と一致するため、この文字列は回文であると判断できます。

文字列 "reader" の場合

• 2番目と後ろから2番目の文字までは一致しています。

• しかし、3番目と後ろから3番目の文字（a と d）を比較した時点で不一致となるため、回文ではないと判断されます。

アルゴリズムの実装：2つのポインタを使う

この考え方は再帰でも実装できますが、ここでは2つのポインタを使った方法を紹介します。

• 先頭を指す start ポインタを 0 に、末尾を指す end ポインタを最後のインデックスに設定します。

• 2つの文字を比較し、一致していれば start を1つ進め、end を1つ戻します（これにより2番目と後ろから2番目の文字へ移動し、以降も同様に続けます）。

• False を返すタイミング： 比較中に一致しない文字のペアが見つかった場合、それ以降のインデックスを調べる必要はないため、即座に False を返します。

• True を返すタイミング： 文字列が回文だった場合、2つのポインタが一致する（チェックすべき文字が中央の1文字だけになる）か、start が end を超える（すべての文字の確認が完了する）と、True を返します。

コード例

def isPalindrome(s):
    start = 0
    end = len(s) - 1
    while start < end:
        if s[start] != s[end]:
            return False
        start += 1
        end -= 1
    return True

print("Enter a string")
st = input()
print(isPalindrome(st))

実行結果

Enter a string
reader
False

Enter a string
madam
True

まとめ

どちらの方法でも回文判定は可能ですが、長い文字列を扱う場合やメモリ効率を重視する場合は、2ポインタ法が有利です。用途に応じて使い分けましょう。