回文判定
回文判定
このレッスンで分かること
- 回文は「文字列の対称性」を判定する問題
- たった 1 行で書けますが、
s[::-1]は 新しい文字列をメモリ上に作る ため、空間計算量がO(n)になります- 回文 とは、前から読んでも後ろから読んでも同じになる文字列のことです
回文判定 とは
文字列が前から読んでも後ろから読んでも同じ「回文」であるかを、双方向ポインタで
O(n)判定する。
回文 とは、前から読んでも後ろから読んでも同じになる文字列のことです。例えば level、racecar、madam などが該当します。hello は逆から読むと olleh で異なるため回文ではありません。回文判定はコーディング面接や競技プログラミングの 入門問題 として頻出するうえ、双方向ポインタ法の練習にも最適です。
回文は「文字列の対称性」を判定する問題。両端からの 2 ポインタで
O(n)に解けるのが本質。
素朴な解法
もっとも単純なのは「逆順にした文字列を作り、元の文字列と比較する」方法です。
Python
def isPalindrome(s):
return s == s[::-1]たった 1 行で書けますが、s[::-1] は 新しい文字列をメモリ上に作る ため、空間計算量が O(n) になります。文字列が非常に長いとメモリを余分に食うのが欠点です。
双方向ポインタによる解法
もっと効率的なのが、左右からインデックスを動かして 1 文字ずつ比較する方法です。
Python
def isPalindrome(s):
left = 0
right = len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True- 空間計算量は
O(1)(追加メモリほぼ不要) - 時間計算量は
O(n) - 違いを見つけたら 即 return で早期終了できる
図で動きを追う
図のポイント (テキスト併記)
- 左右のポインタが中央でぶつかるか、すれ違ったときがループ終了タイミングです
左右のポインタが中央でぶつかるか、すれ違ったときがループ終了タイミングです。長さが偶数なら left == right になることはなく、奇数なら真ん中の 1 文字で left == right になりますが、その文字自身と比較しても結局 true なので比較対象から外せます。
JavaScript での実装
JavaScript
function isPalindrome(s) {
let left = 0;
let right = s.length - 1;
while (left < right) {
if (s[left] !== s[right]) return false;
left += 1;
right -= 1;
}
return true;
}JavaScript も同じロジックです。文字列のインデックス参照は s[i] で 1 文字取得できます。配列と違って書き換え不可ですが、読み取りには問題ありません。
双方向ポインタは「特別ケースを分岐させない」書き方ができる点が美しい。バグも減る。
拡張パターン
実際の面接ではもう一歩進んだ条件が出ることがあります。
- 大文字小文字を無視 したい場合は、比較前に
s.lower()で揃える - 英数字以外を無視 したい場合 (例:
"A man, a plan, a canal: Panama") は、isalnum()でフィルタしてから比較 - Unicode を扱う場合は、JavaScript の
s[i]がサロゲートペアを正しく扱えないことに注意する (Array.from(s)で配列化する)
本問では「英数字のみが入った素の文字列」を対象とするので、これらの追加処理は不要です。
よくある間違い
1 つ目は 空文字列 "" をどう扱うかです。慣習的に空文字列は回文として true とすることが多く、上記実装は left < right で初期から偽になり True を返すので問題ありません。
2 つ目は 1 文字 の文字列です。"a" は明らかに回文 (true) ですが、left = 0, right = 0 で left < right が偽となり即 True を返すので、こちらも自然に通ります。
3 つ目は 長さの偶奇 で挙動を分けようとして条件分岐を増やすことです。両端ポインタなら偶奇を意識せず統一的に書けます。
アルゴリズムを書くときは「特別ケースの分岐」を増やさないシンプルな形を目指す。両端ポインタはまさにその好例。
やってみよう
"level"を双方向ポインタで手で追ってみて、l == l、e == e、最後にv(真ん中) で終わることを確認する。"abca"のような 微妙に違う 文字列でも、2 文字目でfalseが返るかチェック。- 「大文字小文字を区別しない版」を書いてみる (
s.lower()を最初に呼ぶ)。 - 「英数字以外を無視」する版を発展課題として作ってみる。
s = "A man, a plan, a canal: Panama"でtrueになるはず。 - 文字列ではなく 配列 に対しても同じロジックが使えることを確認する。
[1, 2, 3, 2, 1]も「回文配列」と呼べる。
よくある質問
Q. 回文判定の最も簡潔な方法は？
A. Python なら s == s[::-1] の 1 行が最短です。Java/JS は両端からポインタを動かして突き合わせます。大文字小文字・空白・記号を無視するなら、事前に正規化（toLowerCase、replace）してから比較するのが定石です。
Q. アナグラム判定の最速アルゴリズムは？
A. 文字数のカウント配列（英小文字なら 26 個の int 配列）で比較するのが O(n) で最速です。ソート（O(n log n)）よりも僅かに速く、文字種が少ないときに有効です。Unicode 全般を扱うなら HashMap で頻度集計してください。
Q. 応用問題にはどんなものがありますか？
A. 最長回文部分文字列（Manacher 法で O(n)）、回文の数え上げ、グループアナグラム判定などが定番です。LeetCode の Top 100 にも複数含まれており、面接でも頻出のテーマです。
次のレッスン
次は 重複なし最長部分文字列 で、スライディングウィンドウを使って繰り返し文字を含まない最長の部分文字列の長さを O(n) で求める方法を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 回文判定 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 回文判定 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 双方向ポインタ法を使う (s[::-1] による反転比較は不可)
- 空間計算量は O(1) であること
- 空文字列や 1 文字も回文として true を返すこと
入出力例
test-cases.txt
isPalindrome("level") → true
isPalindrome("racecar") → true
isPalindrome("hello") → false
isPalindrome("a") → true
isPalindrome("ab") → false
isPalindrome("aa") → true
isPalindrome("madam") → true
isPalindrome("abca") → false