जांचें कि सी ++ में प्रतिस्थापन के बाद शब्द मान्य है या नहीं

मान लीजिए हमें दिया गया है कि स्ट्रिंग "abc" मान्य है। तो किसी भी वैध स्ट्रिंग वी से, हम वी को दो टुकड़ों एक्स और वाई में विभाजित कर सकते हैं जैसे कि एक्स + वाई वी के समान है। (एक्स या वाई खाली हो सकता है।) फिर, X + "abc" + Y भी मान्य है। तो उदाहरण के लिए S ="abc", फिर मान्य स्ट्रिंग्स के उदाहरण हैं:"abc", "aabcbc", "abcabc", "abcabcababcc"। और अमान्य स्ट्रिंग्स के कुछ उदाहरण हैं:"abccba", "ab", "cababc", "bac"। हमें सत्य की जाँच करनी है यदि और केवल तभी दी गई स्ट्रिंग S मान्य है।

इसलिए यदि इनपुट "abcabcababcc" जैसा है, तो वह मान्य है, इसलिए आउटपुट सत्य होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

स्टैक सेंट को परिभाषित करें
मैं के लिए 0 से S के आकार की सीमा में
- यदि st खाली है या S[i] 'c' के समान नहीं है, तो S[i] को स्टैक में धकेलें
- अन्यथा
  - सेंट में c डालें
  - जबकि सेंट का आकार>=3
    - c :=सेंट के ऊपर और सेंट से शीर्ष तत्व को पॉप करें
    - b :=सेंट के ऊपर और सेंट से शीर्ष तत्व को पॉप करें
    - a:=सेंट के ऊपर और सेंट से शीर्ष तत्व को पॉप करें
    - अस्थायी :=एक के साथ अस्थायी संयोजन
    - अस्थायी:=अस्थायी बी के साथ संयोजित करें
    - अस्थायी:=सी के साथ अस्थायी रूप से संयोजित करें
    - यदि अस्थायी "abc" है, तो अगले पुनरावृत्ति के लिए जाएं
    - अन्यथा
      - a, फिर b, फिर c को 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”