Ở đây chúng ta sẽ thấy một vấn đề thú vị. Chúng ta phải kiểm tra xem một chuỗi có 0 ở giữa 1 hay không. Nếu không, thì chuỗi hợp lệ, ngược lại không hợp lệ. Giả sử có ba chuỗi -
- 10001111010
- 00001111100
- 01111101111
Từ ba chuỗi này, chỉ B là hợp lệ, vì không có số 0 bên trong luồng 1s
Để giải quyết vấn đề này, chúng ta sẽ tìm chỉ mục của 1 đầu tiên hiện diện trong chuỗi và cũng tìm chỉ mục của 1 cuối cùng, sau đó chúng ta sẽ kiểm tra xem có bất kỳ số 0 nào từ hai chỉ số này không, nếu có thì trả về false, ngược lại true (hợp lệ)
Ví dụ
#include <iostream>
using namespace std;
bool hasZeroInOnes(string str) {
int first, last;
for(first = 0; first < str.length(); first++){
if(str[first] == '1')
break;
}
for(last = str.length() - 1; last >= 0; last--){
if(str[last] == '1')
break;
}
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";
}
} Đầu ra
00001111100 is a valid string