【Python】O(1)の追加メモリで文字列内の英字が回文かどうかを判定する方法

はじめに

プログラミングの問題の中には、余分なメモリ（追加スペース）を使わずに解くことが求められるものがあります。今回はその代表例として、「文字列に含まれる英字だけを抜き出したとき、それが回文（前から読んでも後ろから読んでも同じ文字列）になっているかどうかを、O(1)の追加スペースで判定する」方法を解説します。

ここで扱う文字列 s には、小文字のアルファベットだけでなく、記号や数字も含まれる可能性があります。判定の対象となるのは英字のみで、それ以外の文字は無視します。

問題の例

たとえば、入力が次のような文字列だったとします。

s = "ra$5ce58car"

この文字列から英字だけを取り出すと「racecar」となり、これは回文です。したがって、出力は True になります。

解法のアプローチ

余分なスペースを使えないため、新しい文字列を作って反転させるといった手法は使えません。代わりに、両端からポインタを動かす双方向スキャンを行います。具体的な手順は以下の通りです。

補助関数：first_letter_index()

指定された範囲 [left, right] 内を左から右へ走査し、最初に見つかった小文字の英字のインデックスを返します。見つからなければ -1 を返します。

補助関数：last_letter_index()

指定された範囲内を右から左へ走査し、最後に見つかった（つまり右端の）小文字の英字のインデックスを返します。見つからなければ -1 を返します。

メイン処理の流れ

• left を 0、right を文字列の長さ - 1 で初期化し、フラグ flag を True に設定します。
• 文字列の長さ分だけループを回し、以下を繰り返します。
  • left を first_letter_index() で更新（左側の次の英字を探す）。
  • right を last_letter_index() で更新（右側の次の英字を探す）。
  • どちらかのインデックスが負になったら、比較できる英字が残っていないためループを抜けます。
  • str[left] と str[right] が一致していれば、left を +1、right を -1 して次の反復へ。
  • 一致しなければ flag を False にしてループを抜けます。
• 最後に flag の値を返します。

この方法なら、ポインタ変数2つとフラグ1つしか使わないため、追加スペースは O(1) で済みます。

実装コード

それでは、実際のPythonコードを見てみましょう。

def first_letter_index(str, left, right):
    index = -1
    for i in range(left, right + 1):
        if str[i] >= 'a' and str[i] <= 'z':
            index = i
            break

    return index

def last_letter_index(str, left, right):
    index = -1
    for i in range(left, right - 1, -1):
        if str[i] >= 'a' and str[i] <= 'z':
            index = i
            break

    return index

def solve(str):
    left = 0
    right = len(str) - 1
    flag = True

    for i in range(len(str)):
        left = first_letter_index(str, left, right)
        right = last_letter_index(str, right, left)

        if right < 0 or left < 0:
            break
        if str[left] == str[right]:
            left += 1
            right -= 1
            continue

        flag = False
        break

    return flag

s = "ra$5ce58car"
print(solve(s))

実行結果

入力

"ra$5ce58car"

出力

True

計算量について

• 時間計算量： 最悪の場合でも各文字は高々2回走査されるため、O(n) です（n は文字列の長さ）。
• 空間計算量： ポインタとフラグのみを使用するため、O(1) です。

まとめ

この記事では、記号や数字が混在する文字列から英字だけを取り出して回文判定を行う方法を、追加メモリ O(1) という制約のもとで実装しました。ポイントは、新しい文字列を生成せずに左右からの2つのポインタで直接比較することです。このテクニックは、メモリ制約のある環境やコーディング面接で頻出のパターンなので、ぜひ覚えておきましょう。