本サイトABC049C – 白昼夢へは以下から
問題：白昼夢
英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。
- T の末尾に dream dreamer erase eraser のいずれかを追加する。
制約
- 1≦|S|≦105
- S は英小文字からなる。
入力
入力は以下の形式で標準入力から与えられる。
S出力
S=T とすることができる場合YESを、そうでない場合NOを出力せよ。
入力例 1
erasedream出力例 1
YESerase dreamの順で T の末尾に追加することで S=T とすることができます。
入力例 2
dreameraser出力例 2
YESdream eraser の順で T の末尾に追加することで S=T とすることができます。
入力例 3
dreamerer出力例 3
NO解答例
S = input().strip()[::-1]
words = ["dream", "dreamer", "erase", "eraser"]
words = [word[::-1] for word in words]
while len(S) > 0:
matched = False
for word in words:
if S.startswith(word):
S = S[len(word):]
matched = True
break
if not matched:
break
if len(S) == 0:
print("YES")
else:
print("NO")解説
この問題は、与えられた文字列Sが、指定された4つの文字列(dream, dreamer, erase, eraser)を組み合わせて作成できるかどうかを判定するものです。
以下は、この問題を解くためのアプローチです。
- 文字列の逆順の考慮:
- 与えられた文字列
Sを逆順にします。これは、文字列の末尾から操作を行うことが容易であるためです。 - 同様に、4つの文字列も逆順にします。
- 与えられた文字列
- 文字列の探索:
- 逆順にした
Sの末尾から、4つの文字列のいずれかがマッチするかどうかを確認します。 - マッチする文字列が見つかった場合、その文字列の長さだけ
Sを短縮します。 - これを
Sが空になるまで繰り返します。
- 逆順にした
- 結果の出力:
Sが空になった場合、YESを出力します。- そうでない場合、NOを出力します。
以下は、このアプローチを実装したPythonのコードです。
# 入力の受け取り
S = input().strip()[::-1] # 文字列を逆順にする
# 4つの文字列を逆順にする
words = ["dream", "dreamer", "erase", "eraser"]
words = [word[::-1] for word in words]
# 文字列の探索
while len(S) > 0:
matched = False
for word in words:
if S.startswith(word):
S = S[len(word):]
matched = True
break
if not matched:
break
# 結果の出力
if len(S) == 0:
print("YES")
else:
print("NO")【補足1】[::-1]は逆順
Pythonの文字列やリストには、スライスという機能があります。スライスを使用すると、シーケンス(文字列やリストなど)の部分的な要素を取得したり、シーケンスを特定のステップで切り取ったりすることができます。
スライスの基本的な構文は以下の通りです。
sequence[start:stop:step]start: スライスの開始位置を指定します。stop: スライスの終了位置を指定します。この位置の要素は含まれません。step: スライスのステップ数を指定します。この数値によって、何個おきに要素を取得するかを指定します。
[::-1]は、このスライスの構文を使用してシーケンスを逆順にするためのショートカットです。具体的には以下のようになります。
start: 指定されていないので、シーケンスの最後から開始します。stop: 指定されていないので、シーケンスの最初まで進みます。step:-1として指定されているので、1つずつ逆方向に進みます。
したがって、[::-1]を使用すると、シーケンスの要素が逆順になります。
s = "hello"
print(s[::-1]) # 出力: "olleh"この例では、文字列"hello"が[::-1]を使用して逆順になり、"olleh"という新しい文字列が生成されます。
【補足2】# 文字列の探索
# 文字列の探索
while len(S) > 0:
matched = False
for word in words:
if S.startswith(word):
S = S[len(word):]
matched = True
break
if not matched:
breakこのコードは、文字列Sが特定の単語の組み合わせで構成されているかどうかを確認しています。具体的には、文字列Sの先頭から、リストwordsに含まれる単語で始まるかどうかを順番に確認しています。もし、Sがその単語で始まっていれば、その単語をSから取り除きます。このプロセスをSが空になるか、どの単語とも一致しなくなるまで繰り返します。
以下に、このコードの各部分の説明を行います。
while len(S) > 0::Sが空でない限りループを続けます。matched = False: この変数は、Sの現在の先頭がwordsのいずれの単語とも一致しない場合にFalseのままとなります。for word in words::wordsリストの各単語に対してループを実行します。if S.startswith(word)::Sが現在のwordで始まっているかどうかを確認します。S = S[len(word):]: もしSがwordで始まっていれば、そのwordの部分をSから取り除きます。matched = True:Sがwordで始まっていたので、matchedをTrueに設定します。break: 一致した単語が見つかったので、内側のforループを抜けます。if not matched:: もしSの現在の先頭がwordsのどの単語とも一致しなかった場合、この条件がTrueとなります。break: 一致する単語がないため、whileループを終了します。
このコードの目的は、文字列Sがwordsリストの単語の組み合わせで完全に構成されているかどうかを確認することです。もしSが空になれば、それは可能であり、もし途中で一致する単語がなくなれば、それは不可能です。
次の問題へ
前の問題へ
一覧へ
コメント