C++で特定の部分文字列を繰り返し削除し、文字列が空文字列になれるかどうかを判定する方法

2つの文字列 str1 と str2 が与えられているとします。str2 は str1 の部分文字列であり、str1 から削除することができます。また、str2 は str1 内に複数回出現する可能性があります。

この問題の目的は、str1 から str2 を何度も繰り返し削除していったときに、最終的に str1 が空文字列（null string）になるかどうかを判定することです。空文字列にできる場合は 1 を返し、できない場合は 0 を返します。

例えば、入力が str1 = "CCCPPPPPP"、str2 = "CPP" の場合、出力は true（1） となります。

解決アプローチ

この問題は、以下の手順で解くことができます。

• str1 のサイズが 0 より大きい間、以下の処理を繰り返します
  • index := str1 内で str2 が最初に出現する開始位置を取得します
  • index が -1 と等しい場合（str2 が見つからない場合）、ループを抜けます
  • str1 から str2 を削除します
• 最後に、str1 のサイズが 0 であれば 1 を返し、そうでなければ 0 を返します

C++での実装例

以下の実装例を見て、理解を深めましょう。

#include<bits/stdc++.h>
using namespace std;
bool solve(string str1, string str2) {
   while (str1.size() > 0) {
      int index = str1.find(str2);
      if (index == -1)
      break;
      str1.erase(index, str2.size());
   }
   return (str1.size() == 0);
}
int main() {
   string str1 = "CCCPPPPPP", str2 = "CPP";
   cout<<solve(str1, str2)<<endl;
   return 0;
}

入力

"CCCPPPPPP", "CPP"

出力

1

この実装では、標準ライブラリの find() 関数を使って str2 の出現位置を検索し、erase() 関数で該当部分を削除しています。str2 が見つからなくなった時点でループを終了し、残った文字列の長さが 0 かどうかで結果を判定します。