Pythonでバックスペース操作を含むエディタ入力を処理し、最終的なテキストを求めるプログラム

問題の概要

文字列 s が、エディタに入力された一連の文字を表しているとします。ここで、記号「<-」はバックスペース（直前の1文字を削除する操作）を意味します。このとき、すべての入力処理が完了した後のエディタの最終的なテキスト（現在の状態）を求めるのが課題です。

たとえば、入力が s = "ilovepython<-<-ON" の場合、出力は "ilovepythON" になります。「ilovepython」と入力した直後にバックスペースが2回押されているため、末尾の2文字「on」が削除され、その後「ON」が新しく入力されるためです。

解決のためのアプローチ

この問題は、リストをスタックのように使うことでシンプルに解決できます。手順は以下の通りです。

• 結果を格納するための空のリスト res を用意する
• 文字列 s の各文字 i について、次の処理を繰り返す
  • i が「-」で、かつ res の最後の文字が「<」である場合（＝「<-」というバックスペース記号を検出した場合）：
    • res から最後の要素（「<」）を削除する
    • さらに、res が空でなければ、もう1つ最後の要素を削除する（これが実際のバックスペース処理に相当）
  • 上記以外の場合は、文字 i を res の末尾に追加する
• 最後に、res 内のすべての要素を連結した文字列を返す

この方法なら、文字列を一度走査するだけでよいため、計算量は O(n) となり非常に効率的です。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

class Solution:
   def solve(self, s):
      res = []
      for i in s:
         if i == '-' and res[-1] == '<':
            res.pop()
            if res:
               res.pop()
         else:
            res.append(i)
      return "".join(res)

ob = Solution()
print(ob.solve("ilovepython<-<-ON"))

コードのポイント

この実装では、「-」という文字を読み込んだ時点で、その直前に「<」があったかどうかを確認しています。「<-」のペアを検出できたら、まず「<」をリストから取り除き、続けてバックスペースとして1文字削除します。通常の文字であれば、そのままリストの末尾に追加していきます。

入力

"ilovepython<-<-ON"

出力

ilovepythON

まとめ

バックスペースを含む入力のシミュレーションは、スタックの考え方を応用することで簡潔に実装できます。テキストエディタの動作再現や、入力履歴の処理など、さまざまな場面で応用できる基本的なテクニックなので、ぜひ覚えておきましょう。