白昼夢 / Daydream [AtCoder Beginner Contest 049 C]

atcoder.jp

解説には「逆順にすると接頭辞が云々～」と書いてありますが、逆順にしなくても上手くいくみたいです。以下のコードがACコードになります。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		System.out.println (
			sc.next()
			.replace("eraser","").replace("erase","").replace("dreamer","").replace("dream","")
			.equals("")?"YES":"NO"
		);
		
	}
}

eraser → erase → dreamer → dream の順に空文字と置き換えていって、最後に S が空文字になったかどうかで判定します。なぜこの順で処理すると上手くいくのか考えてみます。

eraser と dreamer を比較してみます。この場合、先に処理すべきは eraser です。なぜなら、S が dreameraser だった場合に、dreamer を先に処理してしまうと残りが aser となり、上手くいかないからです。

・eraser > dreamer

eraser と erase では、eraser を先に処理すべきです。S が eraser だった場合、erase を先に処理してしまうと r が残ってしまうからです。また dreamer と erase では、erase を先に処理すべきです。理由は eraser のときと同じです。

・eraser > erase > dreamer

最後に dream ですが、dreamer の後に処理すべきです。S が dreamer だった場合、dream を先に処理してしまうと er が残ってしまうからです。

・eraser > erase > dreamer > dream

という具合で、この順で処理すれば上手くいくということみたいですね。