[AtCoder備忘録記事]AtCoder Beginners Selection ABC049C - 白昼夢

AtCoder Beginners Selection ABC049C - 白昼夢
こちらの問題です。

問題

入出力例

解法

"dreameraser"のようなパターンは前から消していくと全探索でしか対応できませんが、全探索をするとメモリ制限を超過してしまうため、後ろから文字を消していくことで対応します。

#include <iostream>
#include <string>
using namespace std;

bool canForm(string s) {
    while (!s.empty()) {
        if (s.ends_with("dream") || s.ends_with("erase")) {
            // "dream" または "erase" は5文字削除
            s.erase(s.size() - 5);
        } else if (s.ends_with("dreamer") || s.ends_with("eraser")) {
            // "dreamer" は7文字、"eraser" は6文字削除
            if (s.ends_with("dreamer")) {
                s.erase(s.size() - 7);
            } else {
                s.erase(s.size() - 6);
            }
        } else {
            // どれにも一致しない場合は失敗
            return false;
        }
    }
    // 文字列が完全に削除された場合は成功
    return true;
}

int main() {
    string N;
    cin >> N;
    if (canForm(N)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}