二方向ポインタ走査による O(n) 実装
💡 一言で言うと：「文字列から記号やスペースを除き、大文字を小文字に揃えたとき、前から読んでも後ろから読んでも同じかどうかを判定する問題」
💡 この問題を一言で言うと：「文字列から記号やスペースを除き、大文字を小文字に揃えたとき、前から読んでも後ろから読んでも同じかどうかを判定する問題」です。
英語の文章では、大文字・小文字の違いやカンマ・コロン・スペースといった記号が自由に混ざります。この問題では、それらの「見た目のノイズ」を無視して、純粋に英数字（アルファベットと数字）の並びだけに注目したときに回文（前から読んでも後ろから読んでも同じ並び）になっているかを判定します。
⚠️ なぜ単純な方法では解けないのか
s == s[::-1] のような一括比較では正しく判定できません。s = "A man, a plan, a canal: Panama"
→ True
記号とスペースを除いて小文字化すると "amanaplanacanalpanama" となり、前から読んでも後ろから読んでも同じになるため True です。
s = "race a car"
→ False
クリーニングすると "raceacar" となり、逆から読むと "racaecar" で一致しないため False です。
s = " "（半角スペース1文字）
→ True
英数字が1つも無いため、クリーニング後は空文字列になります。空文字列は前からも後ろからも「何もない」ので、回文として扱われ True になります。
入力例 s = "A man, a plan, a canal: Panama" を使って、二方向ポインタが実際にどう動くかを1ステップずつ確認しましょう。文字の下の数字はインデックス（何番目の文字かを示す位置番号）です。
📋 このコードの構造（先に全体像を把握しよう）
from __future__ import annotations
from typing import Final
class Solution:
"""125. Valid Palindrome を解くクラス"""
_MAX_LENGTH: Final[int] = 2 * 10 ** 5
def isPalindrome(self, s: str) -> bool:
"""
文字列 s が英数字だけ・小文字統一で回文かどうかを判定する
Args:
s: 判定対象の文字列
Returns:
回文であれば True、そうでなければ False
"""
if not isinstance(s, str):
raise TypeError("Input must be a string")
if len(s) > self._MAX_LENGTH:
raise ValueError("Input length exceeds the constraint")
left: int = 0
right: int = len(s) - 1
while left < right:
if not s[left].isalnum():
left += 1
continue
if not s[right].isalnum():
right -= 1
continue
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
▶ 入力例 s = "A man, a plan, a canal: Panama" での動作トレース
入力: s = "A man, a plan, a canal: Panama"（長さ30） left=0, right=29 0,29: 'A' と 'a' → 小文字化して比較 → 'a' == 'a' → 一致 → left=1, right=28 1,28: s[1]=' ' は非英数字 → left=2 2,28: 'm' と 'm' → 一致 → left=3, right=27 3,27: 'a' と 'a' → 一致 → left=4, right=26 4,26: 'n' と 'n' → 一致 → left=5, right=25 5,25: s[5]=',' は非英数字 → left=6 6,25: s[6]=' ' は非英数字 → left=7 7,25: 'a' と 'a' → 一致 → left=8, right=24 8,24: s[8]=' ' は非英数字 → left=9 9,24: 'p' と 'P' → 小文字化 'p' == 'p' → 一致 → left=10, right=23 10,23: s[23]=' ' は非英数字 → right=22 10,22: s[22]=':' は非英数字 → right=21 10,21: 'l' と 'l' → 一致 → left=11, right=20 11,20: 'a' と 'a' → 一致 → left=12, right=19 12,19: 'n' と 'n' → 一致 → left=13, right=18 13,18: s[13]=',' は非英数字 → left=14 14,18: s[14]=' ' は非英数字 → left=15 15,18: 'a' と 'a' → 一致 → left=16, right=17 16,17: s[16]=' ' は非英数字 → left=17 left(17) < right(17) は成立しない → ループ終了 出力: True ✅
🗺️ フローチャートの読み方
🔎 入力例 s = "A man, a plan, a canal: Panama" でのフロー追跡
フローの説明：
このフローチャートは、二方向ポインタが「ループ条件のチェック」→「非英数字の読み飛ばし」→「小文字化しての比較」→「ポインタの移動」という4つの処理を繰り返しながら中央へ収束していく様子を表しています。途中で不一致が見つかれば紫のループを抜けて赤い経路で「False を返す」に到達し、一度も不一致がなければ緑の経路で「True を返す」に到達します。
📖 Big-O 記法の読み方（入力サイズ n が大きくなるにつれて処理時間がどう増えるかの目安）
| アプローチ | 時間計算量 | 空間計算量 | 備考 |
|---|---|---|---|
| 二方向ポインタ（採用） | O(n) | O(1) | 新しい文字列を作らないため最省メモリ |
| フィルタ＋反転比較 | O(n) | O(n) | 実装は直感的だが新しい文字列を2つ生成する |
🔍 なぜこの計算量になるのか
時間計算量が O(n) になるのは、left と right という2つのポインタがそれぞれ最大でも文字列の長さ分しか動かず、各文字を高々1回ずつしか読まないためです。空間計算量が O(1) になるのは、追加で使うメモリが left と right という2つの整数変数だけであり、入力文字列の長さが変わってもこの追加メモリの量は変化しないためです。
このページで登場した専門用語を五十音順にまとめました。分からない言葉が出てきたときに参照してください。