TopCoder SRM 598, Division 2, Level 1 : ErasingCharacters

概要

文字列 s が与えられる。
この文字列に対し、以下のアルゴリズムを適用する。

1. i 文字目と i + 1 文字目が等しくなるような i の内最小のものを探す
2. 見つからない場合は終了
3. 見つかった場合は、その二文字を削除して 1 に戻る

適用結果の文字列を求めよ。

解法

問題文のとおりのアルゴリズムを実装すれば解けます。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class ErasingCharacters
{
public:
	string simulate( string s )
	{
		REP( i, 0, s.size() - 1 )
		{
			if ( s[i] == s[ i + 1 ] )
			{
				s.erase( i, 2 );
				return simulate( s );
			}
		}
		return s;
	}
};