キーボードのキーがスタック（連打）した状態で入力された文字列が、意図したターゲット文字列と一致するか判定するPythonプログラム

問題の概要

2つの文字列 s と t があるとします。本来は t を入力したいのですが、キーボードの一部のキーがスタック（押しっぱなし）してしまい、同じ文字が1回以上繰り返し入力されてしまう状況を考えます。

このとき、実際に入力された文字列 s が、もともと t を打とうとした結果としてあり得るものかどうかを判定するのがこの問題です。

例えば、s = "appppleee"、t = "apple" の場合、「a」「pppp」「l」「eee」というように、各キーが1回以上連続で押された結果として t を作れるため、出力は True になります。

解法のアプローチ

この問題は、2つのポインタを使った貪欲法（グリーディー法）で効率的に解くことができます。以下の手順に従います。

• ポインタ i（入力文字列 s 用）と j（ターゲット文字列 t 用）を 0 で初期化する
• s_len := 文字列 s の長さ
• t_len := 文字列 t の長さ
• t_last := 直前に一致した t の文字を記録する変数（初期値は空文字列）

その後、j < t_len の間、以下の処理を繰り返します。

• i == s_len の場合：s を使い切ってしまったのに t が残っているので False を返す
• s[i] == t[j] の場合：t_last を更新し、i と j を両方進める
• s[i] == t_last の場合：キーのスタックによる重複入力なので、i だけ進める
• それ以外の場合：一致しない文字が現れたので False を返す

ループ終了後、i < s_len であれば、s の残りの文字がすべて t_last と同じかどうかを確認します。すべて同じなら True、そうでなければ False です。i == s_len であればそのまま True を返します。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(s, t):
    i = j = 0
    s_len = len(s)
    t_len = len(t)
    t_last = ""
    while j < t_len:
        if i == s_len:
            return False
        if s[i] == t[j]:
            t_last = t[j]
            i += 1
            j += 1
        elif s[i] == t_last:
            i += 1
        else:
            return False
    if i < s_len:
        return all(char == t_last for char in s[i:])
    else:
        return True

s = "appppleee"
t = "apple"
print(solve(s, t))

入力

"appppleee", "apple"

出力

True

計算量について

このアルゴリズムは、文字列 s と t をそれぞれ一度だけ走査するため、時間計算量は O(len(s) + len(t))、空間計算量は O(1) となります。追加のデータ構造を必要としないため、非常に効率的な解法と言えます。