C++での置換後にWordが有効かどうかを確認する

文字列「abc」が有効であると仮定します。したがって、任意の有効な文字列Vから、X + YがVと同じになるようにVを2つの部分XとYに分割できます（XまたはYは空の場合があります）。その場合、X + "abc"+Yも有効です。したがって、たとえばS ="abc"の場合、有効な文字列の例は、 "abc"、 "aabcbc"、 "abcabc"、"abcabcababcc"です。また、無効な文字列の例としては、「abccba」、「ab」、「cababc」、「bac」があります。指定された文字列Sが有効である場合にのみ、trueをチェックする必要があります。

したがって、入力が「abcabcababcc」のような場合、それは有効であるため、出力はtrueになります。

これを解決するには、次の手順に従います-

• スタックstを定義する

• 0からSのサイズまでの範囲のiの場合

  • stが空の場合、またはS [i]が「c」と同じでない場合は、S[i]をスタックにプッシュします

  • それ以外の場合

    • cをstに挿入します

    • stのサイズ>=3

      • c：=stの先頭に移動し、stから一番上の要素をポップします

      • b：=stの先頭で、stから一番上の要素をポップします

      • a：=stの先頭に移動し、stから一番上の要素をポップします

      • temp：=tempは

        と連結します

      • temp：=tempはbと連結します

      • temp：=cと連結するtemp

      • tempが「abc」の場合は、次の反復に進みます

      • それ以外の場合

        • a、b、cの順にstに押し込み、ループを解除します

  • stが空の場合はtrueを返し、それ以外の場合はfalseを返します

理解を深めるために、次の実装を見てみましょう-

例

#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