～ これだけ解けば十分闘える！過去問精選 10 問 ～ の9問目 Daydream をPHPで

はい、前の記事の続きです。

AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ から、9問目。

与えられた文字列が、"dream", "dreamer", "erase", "eraser"を任意に組み合わせることで、できるか判定せよ。という問題。

はっきり言ってしまえば、もっと難しい組み合わせだったら、私は正解できないかもしれません。

こちらの問題の場合は、例えばdreamer…という文字列を先頭の方から見ると、

dream/er…
dreamer/…

どちらか分からないので探索することになります。
この手の問題は苦手です……

ただ、後ろから見れば最後の文字が drea m、eras e、dreame r、erase r でrが2つありますが、後ろから3文字目で見分けがつきますので、判定は可能です。

そんな訳で、4つの単語と末尾を比較して、一致したらどんどん削っていき、何も文字が残らなかったら YES 、何か残っていたら NO と出力するプログラムを書きました。

<?php
$words = ["dream", "dreamer", "erase", "eraser"];

fscanf(STDIN, "%s", $S);

while($S) {
    $flg = false;

    foreach ($words as $word) {
        $len = strlen($word);
        $exam = substr($S, -$len);
        if ($exam === $word) {
            $S = substr($S, 0, strlen($S) - $len);
            $flg = true;
            break;
        }
    }

    if ($flg === false) break;
}

echo $S === "" ? "YES\n" : "NO\n";

前からがダメなら、後ろから行けばいいじゃない？ということで。