Pythonで特定の部分文字列を繰り返し削除し、文字列を空にできるかどうかを判定する方法

2つの文字列 s と t があるとします。s からは t を何度でも削除できますが、1回の操作で削除できるのは1か所だけです。このとき、t を必要な回数だけ削除することで、s を完全に空の文字列にできるかどうかを判定するのが目的です。

例として、s = "pipipinnn"、t = "pin" の場合を考えてみましょう。まず "pipipinnn" から "pin" を1つ削除すると "pipinn" になります。さらに "pin" を削除すると "pin" となり、最後にもう1度 "pin" を削除すれば文字列は空になります。したがって、この場合の出力は True です。

解決のアプローチ

この問題は、次の手順で解くことができます。

• s の長さが 0 より大きい間、以下の処理を繰り返します
  • s 内で t が最初に出現する位置（インデックス）を調べる
  • t が見つからない場合（位置が -1 の場合）はループを抜ける
  • t が見つかった場合は、s から t を1回だけ削除する
• ループ終了後、s の長さが 0 になっていれば True を返し、そうでなければ False を返す

実装例

それでは、実際のコードを見てみましょう。

def solve(s, t):
    while len(s) > 0:
        position = s.find(t)
        if position == -1:
            break
        s = s.replace(t, "", 1)
    return len(s) == 0

s = "pipipinnn"
t = "pin"
print(solve(s, t))

入力

"pipipinnn", "pin"

出力

True

コードの解説

このコードでは、Pythonの find() メソッドを使って s 内に t が存在するかどうかを確認しています。find() は部分文字列が見つかった場合にその開始インデックスを返し、見つからない場合は -1 を返します。

部分文字列が見つかった場合は、replace(t, "", 1) を使って t を1回だけ削除します。第3引数に 1 を指定することで、最初に出現した1か所のみが置換される点がポイントです。

この処理を s が空になるまで、あるいは t が見つからなくなるまで繰り返し、最終的に s が空文字列になっているかどうかを len(s) == 0 で判定して結果を返します。

計算量について

最悪の場合、削除のたびに文字列全体を走査するため、時間計算量は O(n²) 程度になります。ここで n は文字列 s の長さです。文字列が短い場合はこのシンプルな実装で十分ですが、非常に長い文字列を扱う場合はスタックを使った効率的な手法なども検討するとよいでしょう。