数値文字列から有効な電話番号を形成できるか判定するC++コード

問題概要

n桁の数字からなる文字列Sが与えられます。「電話番号」とは、桁数がちょうど11桁で、先頭が「8」で始まる番号として定義されます。1回の操作につき、文字列Sから1桁の数字を取り除くことができます。このとき、Sを有効な電話番号に変換できるかどうかを判定してください。

例えば、入力が S = "5818005553985" の場合、出力は True となります。これは、先頭が「8」で始まる11文字の文字列「8005553985」を作り出せるためです。

解法のアプローチ

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

m := S の長さ
S の末尾に '8' を挿入する
もし '8' の位置 <= (m - 11) ならば:
    true を返す
false を返す

ここでポイントとなるのが、文字列の末尾に「8」を追加するテクニックです。これはいわゆる「番兵（センチネル）」として機能し、元の文字列に「8」が1つも存在しない場合でも、find関数が必ず有効な位置を返すようになり、条件分岐をシンプルに書くことができます。

最初に見つかった「8」の位置が (m − 11) 以下であれば、その「8」以降に少なくとも11文字残っていることを意味します。つまり、不要な数字を取り除けば、先頭が「8」の11桁の電話番号を構成できるということです。

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
bool solve(string S){
    int m = S.size();
    S.push_back('8');
    if ((int(S.find('8')) <= (m - 11)))
        return true;
    return false;
}
int main(){
    string S = "5818005553985";
    cout << solve(S) << endl;
}

入力例

"5818005553985"

出力例

1

動作の解説

入力例 "5818005553985" の場合、文字列の長さ m = 13 です。最初に現れる「8」はインデックス1の位置にあり、条件式は 1 ≤ (13 − 11) = 2 となり成立します。したがって、先頭の余分な数字を取り除けば「8005553985」という有効な電話番号が作れるため、true（1）が返されます。

計算量

find関数が文字列を一度走査するため、時間計算量は O(n) です。また、必要な追加の作業領域は定数程度で済むため、非常に効率的なアルゴリズムと言えます。