C++で長押しされた名前かどうかを判定する方法

問題の概要

ある人がキーボードで名前を入力している場面を考えてみましょう。入力中にボタンを誤って長押ししてしまうことがあり、その結果、本来の文字数よりも多くの同じ文字が入力されてしまうことがあります。

そこで、2つの文字列を受け取り、2番目の文字列（typed）が1番目の文字列（name）を長押しして入力した結果になっているかどうかを判定するプログラムを作成します。

例えば、元の名前が「Amit」で、2番目の文字列が「Ammittt」であれば、これは長押しによって生じた文字列とみなせます。一方、「Ammttt」は「i」という文字が含まれていないため、長押しとは判定できません。

解法のアプローチ

この問題は、2つのポインタ（インデックス）を使うことで効率的に解くことができます。片方のポインタでtyped文字列を走査し、もう片方のポインタで元の名前のどこまで照合できたかを追跡します。

具体的な手順は以下の通りです。

• j を 0 で初期化する
• i を 0 から second.size() 未満まで1ずつ増やしながら、以下を繰り返す
  • j が actual_name のサイズ未満であり、actual_name[j] と second[i] が一致する場合は、j を1増やす
• ループ終了後、j == actual_name.size() であれば true を、そうでなければ false を返す

つまり、typed文字列を先頭から順に調べ、元の名前に含まれるべき文字が正しい順序で現れているかを確認していきます。すべての文字が消費されれば、その文字列は長押しによって生成されたものだと判断できます。

実装例

理解を深めるために、次のC++による実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool isLongPressedName(string name, string typed) {
        int j = 0;
        for(int i = 0; i < typed.size(); i++){
            if(j < name.size() && name[j] == typed[i])j++;
        }
        return j == name.size();
    }
};
main(){
    Solution ob;
    string res = ob.isLongPressedName("Amit", "Ammittt") ? "true" :
    "false";
        cout << res;
}

入力

"Amit"
"Ammittt"

出力

true

計算量について

このアルゴリズムは、typed文字列を一度だけ走査するため、時間計算量は O(n)、追加の記憶領域は定数 O(1) で済みます。非常にシンプルかつ効率的な手法です。