C++でバイナリ文字列の「1」が必ず2個連続して現れるかどうかを判定する方法

今回は、もう一つ興味深い問題を取り上げます。次の条件を満たすバイナリ文字列を受け取り、それが有効かどうかを判定するコードを作成します。

• 連続する「1」のグループは、必ず長さ2であること
• 連続する「1」のグループは、必ず1つ以上の「0」の後に出現すること

たとえば「0110」という文字列は条件を満たす有効な文字列ですが、「001110」（1が3個連続している）や「010」（1が1個だけ）は無効となります。

アプローチ

考え方はシンプルです。文字列中の「1」の出現位置を順番に検索し、それぞれが部分文字列「011」の一部として正しい形で現れているかを確認します。どれか一つでも条件を満たさない箇所があれば false を返し、すべてのチェックを通過できれば true を返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
bool isValidStr(string str) {
    int n = str.length();
    int index = find(str.begin(), str.end(), '1') - str.begin();
    if (index == 0) // 文字列が「1」で始まる場合は無効
        return false;
    while (index <= n - 1) {
        if (str[index - 1] != '0') // 「1」の直前が「0」でない場合は無効
            return false;
        if (index + 1 < n && str[index + 1] != '1') // 「1」の直後にもう一つの「1」がない場合は無効
            return false;
        if (index + 2 < n && str[index + 2] == '1') // 「0111」のように1が3個以上続く場合は無効
            return false;
        if (index == n - 1) // 文字列が単独の「1」で終わる場合は無効
            return false;
        index = find(str.begin() + index + 2, str.end(), '1') - str.begin();
    }
    return true;
}
int main() {
    string str = "011000110110";
    if(isValidStr(str)){
        cout << str << " is a valid string";
    } else {
        cout << str << " is NOT a valid string";
    }
}

出力結果

011000110110 is a valid string

ロジックの解説

このプログラムでは、以下の5つのチェックを行うことで文字列の妥当性を検証しています。

• 先頭チェック： 文字列が「1」で始まっている場合、「0」の後に「1」が現れるというルールに反するため無効です。
• 直前チェック： 見つけた「1」の直前が「0」でなければ、その「1」は正しい位置に出現していないことになります。
• 直後チェック： 「1」の直後にもう一つの「1」が続いていなければ、グループの長さが1となり無効です。
• 3連続チェック： 「0111」のように3個以上の「1」が続くパターンも無効です。
• 末尾チェック： 文字列が単独の「1」で終わっている場合も、ペアが成立しないため無効です。

各チェックを通過したら、find 関数を使って次の「1」の位置へジャンプし、同じ検証を繰り返します。この処理により、文字列全体を一度の走査で効率的に判定できます。