C++で置換後に文字列が有効かどうかを判定するアルゴリズム

文字列「abc」が有効(valid)であると定義します。さらに、任意の有効な文字列Vを2つの部分XとYに分割できるとき(X + Y = V、XまたはYは空でも可)、X + "abc" + Y もまた有効な文字列となります。

例えば S = "abc" の場合、有効な文字列の例としては「abc」「aabcbc」「abcabc」「abcabcababcc」などが挙げられます。一方、「abccba」「ab」「cababc」「bac」などは無効な文字列です。この記事では、与えられた文字列Sが有効である場合にのみtrueを返すプログラムをC++で実装します。

例えば、入力が「abcabcababcc」の場合、これは有効な文字列なので、出力はtrue(1)になります。

解法のアプローチ:スタックを活用する

この問題は、スタック(stack)を使うことで効率的に解けます。基本的な考え方は、「'c'が出現したタイミングで、スタックの上位3要素が'abc'になっているかを確認する」というものです。もし'abc'になっていれば、それらをスタックから取り除き(= 挿入操作を逆にたどる)、なっていなければその時点で無効と判断できます。

具体的な手順は以下の通りです。

• スタックstを定義する
• iを0からSのサイズまでループさせる
  • スタックが空、またはS[i]が'c'でない場合は、S[i]をスタックにプッシュする
  • S[i]が'c'の場合は、以下を実行する
    • 'c'をスタックにプッシュする
    • スタックのサイズが3以上である間、以下を繰り返す
      • c := スタックの先頭要素を取得してポップ
      • b := スタックの先頭要素を取得してポップ
      • a := スタックの先頭要素を取得してポップ
      • temp := a、b、cをこの順に連結した文字列
      • tempが"abc"と等しければ、次の反復へ進む
      • 等しくなければ、a、b、cの順にスタックへ戻してループを抜ける
• すべての処理終了後、スタックが空であればtrueを返し、そうでなければfalseを返す

このアルゴリズムの計算量はO(n)(nは文字列の長さ)、空間計算量もO(n)となり、非常に効率的です。

C++による実装例

#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

まとめ

スタックを用いることで、「abc」の挿入操作によって構築可能な文字列かどうかを線形時間で判定できます。ポイントは、'c'を読み込んだ瞬間に直前の3文字が"abc"パターンと一致するかを検証し、一致すれば消去(ポップ)、一致しなければ即座に無効と判断する点です。最終的にスタックが空になれば、その文字列は有効であると結論付けられます。