Sau đây chúng ta sẽ thấy một vấn đề thú vị khác. Chúng ta phải viết mã chấp nhận một chuỗi, có các tiêu chí sau.
- Mọi nhóm gồm các số 1 liên tiếp, phải có độ dài là 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
Giả sử có một chuỗi như 0110, đây là chuỗi hợp lệ, cho dù 001110, 010 không hợp lệ
Đây là cách tiếp cận đơn giản. chúng ta phải 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 không thành công, đối với bất kỳ chuỗi con nào thì trả về false, ngược lại là true.
Ví dụ
#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) //when the string starts with 1, then return false
return false;
while (index <= n - 1) {
if (str[index - 1] != '0') // If 1 doesn't appear after an 0
return false;
if (index + 1 < n && str[index + 1] != '1') // If '1' is not succeeded by another '1'
return false;
if (index + 2 < n && str[index + 2] == '1') // If sub-string is of the type "0111"
return false;
if (index == n - 1) // If str ends with a single 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";
}
} Đầu ra
011000110110 is a valid string