🎉
ABC 349 C - Airport Codeを理解し忘れないようにする。
問題概要
文字列SがTの連続とは限らない部分文字列かどうかを判定する。
現状(WAのコード)
rep(i,3) {
rep(j,n) {
if (used[j]) continue;
char k = t[i]+32;
if (s[j] == k) {
used[j] = true;
ans++;
break;
}
}
}
t[0]==s[2]、t[1]==s[1]の時にans++されるので、部分文字列の順番が考慮されていない。例えば以下のケースの場合に通らない。
srba
BRS
// Noが出力されるのが正しいがYesが出力される。
Sはbrsが含まれているが、順番がTと合っていない。
上記コードを改善するのも手だが、解説放送のコードを参考にする。
解き方
auto isSubArray = [&](string x)->bool {
int xi = 0;
for(char c:s) {
// 懸念点
if (x[xi] == c) xi++;
if (xi == x.size()) return true;
}
return false;
};
このisSubArray関数では引数xにTが入る。
S[i]にT[xi]が合致するたびにxi+1するので順番が合う
Discussion