爆弾文字列の除去とは？
文字列の中に決められた『爆弾パターン』が連続で現れるたびにその部分を除去し、両側がくっついてまたできるパターンまですべて消えるまで繰り返す問題です。
例えばゼリー列 "mirkAAkkx" で爆弾パターンが "kk" なら、真ん中の kk がポンと弾けて "mirkAAx" が残ります。
なぜスタックなのか？
最も単純な方法は「パターンを探して消し、最初からやり直す」を繰り返すことです。しかしこれだと除去のたびに文字列全体を再走査するため、最悪の場合O(n²)以上になりとても遅くなります。
核心: 爆発は常に今積んだばかりの末尾で起こります。前の部分はすでに検査済みで、新しい文字が入って新しいパターンができるなら、それは必ず末尾でできます。
だからスタックを使います。文字を一つずつ積み、スタック上部のK個が爆弾パターンと一致した瞬間にそのK個を一度にpopします。両側がくっついて起こる連鎖爆発も自動的に処理されます——popした後、その下にあった文字が自然に新しい末尾になるからです。
動作原理
ステップ1. 文字を左から一つずつスタックにpushします。
ステップ2. push直後、入れた文字が爆弾パターンの最後の文字と同じか確認します。（違えばパターンは完成しないので比較自体をスキップ——小さな最適化）
ステップ3. 同じならスタック末尾K個を爆弾パターンと比較します。
- •一致: 末尾K個をpop（ポン！）
- •不一致: そのまま残す。
ステップ4. 最後まで進めた後、スタックに残った文字が答えです。空なら "EMPTY"。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(n) |
| 空間 | O(n) |
各文字は最大一度push、最大一度popされます。文字列を一度だけ走査するので全体でO(n)です。
よくあるミス
- •毎回最初から再検査: パターンを消した後にインデックス0から再スキャンするとO(n²)。スタックで末尾だけを見ましょう。
- •文字列replaceの繰り返し:
while (s.contains(bomb)) s = s.replace(...)は直感的ですがとても遅いです。 - •毎文字でK個比較: 入れた文字がパターン最後の文字と違えば比較をスキップして定数を減らせます。
AlgoNoteで直接確認しましょう
文字がスタックに一つずつ積まれ、末尾が爆弾パターンと一致した瞬間にポンと弾ける過程を、AlgoNoteでステップごとに確認できます。