Kiểm tra chuỗi nhị phân có hai số 1 liên tiếp xuất hiện mọi nơi trong C++

Chúng ta sẽ xem xét một bài toán thú vị. Cần viết mã chấp nhận một chuỗi thỏa mãn các tiêu chí sau:

• Mỗi nhóm các số 1 liên tiếp phải có độ dài bằng 2
• Mỗi nhóm các số 1 liên tiếp phải xuất hiện sau 1 hoặc nhiều số 0

Ví dụ: chuỗi "0110" là hợp lệ, trong khi "001110" và "010" không hợp lệ.

Cách tiếp cận đơn giản: tìm các lần xuất hiện của '1' và kiểm tra xem nó có phải là một phần của chuỗi con "011" hay không. Nếu điều kiện thất bại cho bất kỳ chuỗi con nào thì trả về false, ngược lại trả về true.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;

bool laChuoiHopLe(string str) {
    int n = str.length();
    int index = find(str.begin(), str.end(), '1') - str.begin();
    if (index == 0) // khi chuỗi bắt đầu bằng 1, trả về false
        return false;
    while (index <= n - 1) {
        if (str[index - 1] != '0') // Nếu 1 không xuất hiện sau 0
            return false;
        if (index + 1 < n && str[index + 1] != '1') // Nếu '1' không được theo sau bởi '1' khác
            return false;
        if (index + 2 < n && str[index + 2] == '1') // Nếu chuỗi con kiểu "0111"
            return false;
        if (index == n - 1) // Nếu chuỗi kết thúc bằng một 1 đơn lẻ
            return false;
        index = find(str.begin() + index + 2, str.end(), '1') - str.begin();
    }
    return true;
}

int main() {
    string str = "011000110110";
    if(laChuoiHopLe(str)){
        cout << str << " là một chuỗi hợp lệ";
    } else {
        cout << str << " KHÔNG phải là chuỗi hợp lệ";
    }
}

Kết quả đầu ra

011000110110 là một chuỗi hợp lệ