正しい回文チェック
両端から効率よく比較します
「正しい回文チェック」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
回文とは
回文は、前から読んでも後ろから読んでも同じになる文字列です。racecarやlevelがその例で、回文判定は定番の入門問題です。🔁
スライスのテクニック
Pythonでは、スライスs[::-1]を使って文字列を反転できます。元の文字列と比較すれば、1行で判定できます。
s = 'level'
print(s == s[::-1]) # Trueスライスは追加メモリを消費する
スライスを使う方法は短く書けますが、反転した文字列全体のコピーを作成します。非常に長い文字列では、この追加メモリが制限に影響することがあります。
2ポインタを使う方法
1つのポインタを先頭に、もう1つを末尾に置きます。両端を比較し、中央へ向かって進めます。追加の使用メモリはO(1)です。
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
break
i += 1; j -= 1中央で止める
ポインタは中央まで進めれば十分です。iがj以上になったら、すべての組の一致が確認でき、文字列は回文です。
不一致なら早期終了する
2ポインタのループでは、組が異なった瞬間にreturn Falseできます。文字列全体を走査せずに済むことが多く、高速化につながります。
def is_pal(s):
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]: return False
i += 1; j -= 1
return TrueどちらもO(n)
どちらの方法でも各文字には最大1回しか触れないため、どちらも線形時間で実行されます。違いは追加で使用するメモリだけです。
先に正規化する
多くの問題では、大文字小文字や空白を無視します。先に文字列を整えるため、小文字に変換し、文字と数字だけを残します。
raw = 'A man, a plan'
clean = ''.join(c.lower() for c in raw if c.isalnum())整えた文字列をチェックする
正規化したら、整形済みの文字列に通常の回文判定を適用します。文の回文を判定する標準的なパターンです。
print(clean == clean[::-1])ポインタで文字以外を飛ばす
先に文字列を整える代わりに、2ポインタで英数字以外の文字をその場で飛ばすこともできます。これなら2つ目の文字列を作る必要がありません。
部分文字列の回文
より難しい問題では、回文になっている部分文字列を扱います。基本となる考え方は中心から拡張することです。両端が一致する間、各位置から外側へ広げます。
クイックチェック
回文判定について、1問確認しましょう。
まとめ
これで、すばやいスライスやメモリ効率のよい2ポインタを使って回文を判定し、判定前に複雑な入力を正規化できるようになりました。🎉
AI チューターと学ぶ Coding Interview Prep — 無料
ブラウザでリアルコードを書いて実行し、24/7 の AI チューターから瞬時にサポートを受け、ウェブまたはアプリで続きから学習できます。
- コース
- 90
- レッスン
- 360
よくある質問
「正しい回文チェック」レッスンは無料ですか？
はい。「正しい回文チェック」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「正しい回文チェック」で何を学びますか？
両端から効率よく比較します ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「正しい回文チェック」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。