এখানে আমরা একটি আকর্ষণীয় সমস্যা দেখব। আমাদের একটি স্ট্রিং গ্রহণ করতে হবে যেটি নিম্নলিখিত শর্তাবলী পূরণ করে:
- লগাতার ১ গুলোর প্রতিটি গোষ্ঠীর দৈর্ঘ্য অবশ্যই ২ হতে হবে
- লগাতার ১ গুলোর প্রতিটি গোষ্ঠী অবশ্যই ১ বা তার অধিক ০ এর পরে আসতে হবে
মনে করুন "০১১০" এর মতো একটি স্ট্রিং আছে, এটি বৈধ স্ট্রিং, কিন্তু "০০১১১০", "০১০" ইত্যাদি বৈধ নয়।
এখানে পদ্ধতিটি সহজ। আমাদের ১ এর আবির্ভাব খুঁজে বের করতে হবে এবং যাচাই করতে হবে যে এটি "০১১" সাব-স্ট্রিং-এর অংশ কিনা। যদি কোনো সাব-স্ট্রিং-এর জন্য শর্তটি ব্যর্থ হয়, তবে false রিটার্ন করব, অন্যথায় true।
উদাহরণ (C++ কোড)
#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) // যখন স্ট্রিং ১ দিয়ে শুরু হয়, তবে false রিটার্ন করো
return false;
while (index <= n - 1) {
if (str[index - 1] != '0') // যদি ১ কোনো ০-এর পরে না আসে
return false;
if (index + 1 < n && str[index + 1] != '1') // যদি '১' এর পরে আরেকটি '১' না থাকে
return false;
if (index + 2 < n && str[index + 2] == '1') // যদি সাব-স্ট্রিং "০১১১" টাইপের হয়
return false;
if (index == n - 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
