問題概要
英大文字からなる文字列 word が与えられる。word が以下の条件を共に満たすかどうかを判定せよ。
- 同じ文字が連続しない
- ある二つの文字 x, y (同一でもよい)があって、xyxy となる部分列が存在しない
解法
word の長さを L と書きます。
それぞれの条件は互いに独立なので、それぞれ別に判定することを考えます。
一つ目の条件は、各 i ( 0 ≦ i < L - 1 ) について、word[ i ] と word[ i + 1 ] が異なることを確かめることで判定できます。これは単純なループにより で完了します。
二つ目の条件は、長さ 4 の部分列を全て試して、xyxy なるものが存在するかを確かめることで判定できます。すなわち、各 i, j, k, l ( 0 ≦ i < j < k < l < L ) について、word[ i ] == word[ k ] && word[ j ] == word[ l ] を満たすものが存在すれば、二つ目の条件を満たさないと分かります。この処理は できつめですが、定数が軽いので案外余裕で通ります。
コード
#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) class LongWordsDiv2 { public: string find(string word) { return check1( word ) && check2( word ) ? "Likes" : "Dislikes"; } bool check1( const string &S ) { REP( i, 0, S.size() - 1 ) { if ( S[i] == S[ i + 1 ] ) { return false; } } return true; } bool check2( const string &S ) { const int L = S.size(); REP( i, 0, L ) { REP( j, i + 1, L ) { REP( k, j + 1, L ) { REP( l, k + 1, L ) { if ( S[i] == S[k] && S[j] == S[l] ) { return false; } } } } } return true; } };