回文判定

全部を読んでから答える必要はない

回文とは、前から読んでも後ろから読んでも同じになる文字列のことです。level や racecar が回文で、hello は違います。

hello を見てください。最初が h、最後が o。この 1 回の比較で答えは決まりました。真ん中がどうなっていようと関係ありません。

ところが「逆さまにした文字列を作って見比べる」やり方だと、答えが出ているのに全部を複製してから比べ始めます。100 万文字なら、100 万文字ぶんのメモリを新しく確保したうえでです。しかも回文でないほとんどの入力は、たった数文字で決着がついています。判定のために場所を用意するという発想そのものが、割に合っていません。

両端から 1 文字ずつ寄せる

作るのをやめて、見る位置だけを動かします。左の印を先頭、右の印を末尾に置き、その 2 文字を比べます。同じなら左を 1 つ右へ、右を 1 つ左へ寄せます。

level は 2 回の比較で印がぶつかり、その時点で回文と分かります。違う文字に出会ったら、そこで打ち切りです。新しい文字列を 1 つも作らないので、入力がどれだけ長くなっても余分なメモリは増えません。

比較の回数も半分で済みます。1 回の比較で 2 文字ぶんの判定が終わるからです。racecar の 7 文字なら 3 回。逆さまの文字列を作るやり方は、複製に文字数ぶんの手間をかけたうえで、さらに文字数ぶんの比較をします。

同じ考え方は文字列以外にも使えます。[1, 2, 3, 2, 1] のような配列が左右対称かを調べたいときも、印を 2 つ置いて寄せるだけです。位置を指定して中身を取り出せるものなら、何にでも当てはまります。

真ん中の 1 文字は見なくてよい

文字数が奇数だと、印が寄っていったとき同じ 1 文字を指す瞬間があります。level の v です。自分と自分を比べても必ず一致するので、比べる意味がありません。

だから、続ける条件は「左の印が右の印より手前にいる間」で足ります。偶数なら印はすれ違って止まり、奇数なら重なって止まる。どちらも同じ条件で正しく終わります。文字数の偶数と奇数で処理を分けたくなりますが、その分岐は不要です。

空文字列と 1 文字も同じ形で扱えます。どちらも最初から条件が成り立たないので、比較を一度もせずに回文と答えます。特別扱いを書き足す必要はありません。

よくある間違い

右の印を len(s) から始めることです。位置の番号は 0 から数えるので、最後の文字がいるのは len(s) - 1 です。1 つ多いところを読むと、その場で例外になります。

1. 双方向ポインタ法を使う (s[::-1] による反転比較は不可)
2. 空間計算量は O(1) であること
3. 空文字列や 1 文字も回文として true を返すこと