Chúng ta sẽ xem xét một bài toán thú vị. Cần kiểm tra xem một chuỗi có chứa số 0 ở giữa các số 1 hay không. Nếu không có, chuỗi hợp lệ; ngược lại không hợp lệ.
Giả sử có ba chuỗi:
- 10001111010
- 00001111100
- 01111101111
Trong ba chuỗi này, chỉ chuỗi B (00001111100) là hợp lệ vì không có số 0 nào nằm trong dãy các số 1.
Để giải quyết: tìm chỉ số của số 1 đầu tiên và số 1 cuối cùng trong chuỗi. Sau đó kiểm tra xem có số 0 nào giữa hai chỉ số này không. Nếu có thì trả về false, ngược lại true.
Ví dụ mã C++
#include <iostream>
using namespace std;
bool coZeroGiuaHaiMot(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(coZeroGiuaHaiMot(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
00001111100 là một chuỗi hợp lệ