SRM 666 Div2 Medium GoodString

問題

SRM 666 - TopCoder Wiki

文字列"ab"を既存の文字列の任意の位置に挿入する,この操作を繰り返して得られる文字列を"Good"とする. 任意の文字列が与えられた時,その文字列が"Good"か否かを求める問題.

解答

  • Goodな文字列はabを繰り返し挿入することによって作られた文字列なので少なくとも1つ"ab"が出現する
  • Goodな文字列から任意のabを取り除いた文字列もGoodな文字列である
  • 上記から繰り返しabを取り除いて,空文字列になればGood,そうでなければGoodではないと判別できる
class GoodString
{
public:
  string isGood(string s)
    {
      string cur = s;
      while(cur.size() > 0) {
        size_t pos = cur.find("ab");
        if (pos == std::string::npos) return "Bad";
        // cout << "pos=" << pos << endl;
        cur = cur.substr(0, pos) + cur.substr(pos+2);
      }
      return "Good";
    }
};