Pythonで文字列tが文字列sの長押しタイピング結果かどうかを判定する方法

2つの小文字のみで構成された文字列 s と t があるとします。タイピング中に母音のキーをうっかり長押しすると、その母音が1回以上繰り返し入力されることがあります。ここでは、t が「s を長押し込みで入力した結果」となり得るかどうかを判定する方法を解説します。

たとえば、s = "mine"、t = "miiine" という入力の場合、母音 i が3回繰り返されていますが、それ以外の文字は変化していないため、出力は True になります。

解決のための手順

この問題は、両方の文字列を先頭から同時に走査し、対応する文字ごとの連続出現回数を比較することで解決できます。具体的な手順は以下の通りです。

• s_len ← 文字列 s の長さ
• t_len ← 文字列 t の長さ
• j ← 0(t 側の走査位置)
• i を 0 から s_len - 1 まで繰り返します。
  • s[i] と t[j] が一致しない場合は False を返します。
  • s[i] が母音でない場合は、j を1つ進めて次の反復へ移ります。
  • cnt_1 ← 1 とし、s[i] と s[i+1] が等しい限り cnt_1 を加算しながら i を進めます(s 内での連続出現回数)。
  • cnt_2 ← 1 とし、t[j] と s[i] が等しい限り cnt_2 を加算しながら j を進めます(t 内での連続出現回数)。
  • cnt_1 > cnt_2 の場合、つまり s 側の連続回数の方が多い場合は False を返します。
• すべての文字を確認できたら True を返します。

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

実装例(Python)

def isVowel(c):
    vowel = "aeiou"
    return c in vowel

def solve(s, t):
    s_len = len(s)
    t_len = len(t)
    j = 0
    for i in range(s_len):
        if s[i] != t[j]:
            return False
        if isVowel(s[i]) == False:
            j = j + 1
            continue
        cnt_1 = 1
        while i < s_len - 1 and (s[i] == s[i + 1]):
            cnt_1 = cnt_1 + 1
            i = i + 1
        cnt_2 = 1
        while j < t_len - 1 and t[j] == s[i]:
            cnt_2 = cnt_2 + 1
            j = j + 1
        if cnt_1 > cnt_2:
            return False
    return True

s = "mine"
t = "miiine"
print(solve(s, t))

入力

"mine", "miiine"

出力

True

まとめ

このアルゴリズムは、文字列 s と t をそれぞれ一度ずつ走査するだけなので、計算量は O(len(s) + len(t)) と非常に効率的です。ポイントは、子音は長押しで繰り返されないため厳密に1対1で対応させる一方、母音については t 側の連続出現回数が s 側以上であればよい、という条件で判定する点にあります。