問題概要
文字列に対して,以下の操作を考える
- 文字列のどこか(先頭,末尾も許容)に,文字列 "ab" を挿入する
空文字列から始めてこの操作を複数回適用することで,文字列 $S$ を作ることができるか?
- $1 \leq |S| \leq 50$
- $S_i \in \{ \mathrm{ `a', `b' } \}$
解法
構成された文字列に於いて,同時に挿入された 'a', 'b' の組について考えてみると,'a', 'b' の位置関係(前後)は変わらず,間に 0 文字以上が挿入されている状態になっていることが分かります.空文字列から構成可能な文字列を valid な文字列と呼ぶことにすると,この間に入っている文字列もまた valid です(間の部分には始め空文字列があって,そこに操作を加えていると考える).また,先頭や末尾に挿入することは,valid な文字列を連結していると考えられます.ここから valid な文字列の条件を考えてみると,
- 空文字列は valid
- 文字列 $x$ が valid なとき,$\mathrm{ ``a'' } + x + \mathrm{ ``b''}$ は valid
- 文字列 $x, y$ が valid なとき,$x + y$ は valid
となります.これは,'a' を '(' に,'b' を ')' に置き換えて考えると「括弧がバランスしていること」の定義そのものです.従って,同じアルゴリズムで解くことができます.
括弧がバランスしていることのチェックは,文字列を先頭から舐めながら
- '(' がきたら深さを +1
- ')' がきたら深さを -1
として,深さ 0 から始めて途中で負にならず,終了時 0 ならばバランスしていることが分かります(スタックを用いる方法と同じことです).
このアルゴリズムは,文字列を走査して文字ごとに定数時間の処理をしているので $O( |S| )$ 時間で実行できます.
コード
#define FOR( e, c ) for ( auto &e : c ) const char *MSG[] = { "Bad", "Good" }; class GoodString { public: string isGood( string s ) { int depth = 0; FOR( c, s ) { if ( c == 'a' ) { ++depth; } else { --depth; } if ( depth < 0 ) { return *MSG; } } return MSG[ depth == 0 ]; } };