ধরুন আমাদের দেওয়া হল যে "abc" স্ট্রিংটি বৈধ। সুতরাং যেকোন বৈধ স্ট্রিং V থেকে, আমরা V কে X এবং Y দুটি ভাগে ভাগ করতে পারি যাতে X + Y V এর মতই হয়। (X বা Y খালি হতে পারে)। তারপর, X + "abc" + Yও বৈধ। সুতরাং উদাহরণস্বরূপ S ="abc", তারপর বৈধ স্ট্রিংগুলির উদাহরণ হল:"abc", "aabcbc", "abcabc", "abcabcababcc"। এবং অবৈধ স্ট্রিংগুলির কিছু উদাহরণ হল:"abccba", "ab", "cababc", "bac"। প্রদত্ত স্ট্রিং S বৈধ কিনা এবং শুধুমাত্র তা হলেই আমাদের সত্য পরীক্ষা করতে হবে।
তাই ইনপুট যদি "abcabcababcc" এর মত হয়, তাহলে সেটি বৈধ, তাই আউটপুট সত্য হবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি স্ট্যাক স্ট্যাক সংজ্ঞায়িত করুন
-
আমি 0 থেকে S
এর পরিসরে-
যদি st খালি হয় বা S[i] 'c' এর মতো না হয়, তাহলে S[i] কে স্ট্যাকের মধ্যে চাপুন
-
অন্যথায়
-
st
-এ c ঢোকান -
যখন st>=3
এর আকার-
c :=st এর শীর্ষ এবং st
থেকে শীর্ষ উপাদান পপ করুন -
b :=st এর শীর্ষ এবং st
থেকে শীর্ষ উপাদান পপ করুন -
a :=st এর শীর্ষ এবং st থেকে উপরের উপাদান পপ করুন
-
temp :=a
এর সাথে temp সংযুক্ত করুন -
temp :=b
এর সাথে temp সংযুক্ত করুন -
temp :=temp এর সাথে c
সংযুক্ত করুন -
যদি তাপমাত্রা "abc" হয়, তাহলে পরবর্তী পুনরাবৃত্তির জন্য যান
-
অন্যথায়
-
a, তারপর b, তারপর c st এ ধাক্কা দিন এবং লুপ ভাঙ্গুন
-
-
-
-
সত্য ফেরত দিন, যখন st খালি থাকে, অন্যথায় মিথ্যা ফেরত দিন
-
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isValid(string S) {
stack <char> st;
for(int i = 0; i < S.size(); i++){
if(st.empty() || S[i] != 'c'){
st.push(S[i]);
}else{
st.push('c');
while(st.size() >= 3){
char c = st.top();
st.pop();
char b = st.top();
st.pop();
char a = st.top();
st.pop();
string temp = "";
temp += a;
temp += b;
temp += c;
if(temp == "abc"){
continue;
}else{
st.push(a);
st.push(b);
st.push(c);
break;
}
}
}
}
return st.empty();
}
};
main(){
Solution ob;
cout << (ob.isValid("abcabcababcc"));
} ইনপুট
“abcabcababcc”
আউটপুট
1
