【C++入門】バイナリ文字列の「1」の間に「0」が含まれているかを判定する方法

今回は少し面白い文字列処理の問題を取り上げます。与えられたバイナリ文字列（0と1のみで構成された文字列）について、「1」の並びの中に「0」が挟まっていないかどうかを判定します。「0」が含まれていなければその文字列は有効（valid）、含まれていれば無効（invalid）とみなします。

問題の例

次の3つの文字列を見てみましょう。

• A：10001111010
• B：00001111100
• C：01111101111

この中で有効なのは B の「00001111100」だけです。B は先頭から最初の「1」まで、そして最後の「1」以降には「0」がありますが、連続する「1」のブロック内部には「0」が一切存在しないためです。一方、A は「1」の間に複数の「0」が混在し、C も途中に「0」が挟まっているため無効となります。

解決のアプローチ

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

1. 文字列内で最初に現れる「1」のインデックスを探す。
2. 最後に現れる「1」のインデックスを探す。
3. この2つのインデックスの間に「0」が1つでも存在するかを確認する。

間に「0」が見つかれば false（無効）を返し、見つからなければ true（有効）を返します。文字列を先頭から末尾まで数回走査するだけで済むため、計算量は O(n)、追加のメモリは O(1) という効率的なアルゴリズムになります。

C++による実装例

#include <iostream>
using namespace std;

bool hasZeroInOnes(string str) {
    int first, last;
    // 最初の「1」の位置を前方から探索
    for(first = 0; first < str.length(); first++){
        if(str[first] == '1')
            break;
    }
    // 最後の「1」の位置を後方から探索
    for(last = str.length() - 1; last >= 0; last--){
        if(str[last] == '1')
            break;
    }
    // 最初と最後の「1」の間に「0」がないかチェック
    for(int i = first + 1; i < last; i++){
        if(str[i] == '0')
            return false;
    }
    return true;
}

int main() {
    string str = "00001111100";
    if(hasZeroInOnes(str)){
        cout << str << " is a valid string";
    } else {
        cout << str << " is NOT a valid string";
    }
}

実行結果

00001111100 is a valid string

補足ポイント

• 文字列に「1」が1つも含まれない場合や「1」が1個しかない場合も、このコードではループ条件により自然に true（有効）が返されるため安全です。
• 判定対象は最初の「1」から最後の「1」までの区間のみなので、前後の余分な「0」は結果に影響しません。

このように、文字列の両端にある「1」の位置を特定して間を走査するだけで、シンプルかつ高速にバイナリ文字列の妥当性を検証できます。