AtCoder 過去問「ABC049C - 白昼夢」を解いてみた

はじめに

Python の練習として AtCoder の過去問「ABC049C - 白昼夢」を解いてみました.

もちろん, 優れた解説はたくさんあるので, そちらと見比べてください.

再帰で解いたら, 案の定…

まず, 再帰で解いてみました. 与えられた文字列が, dream, dreamer, erase, eraser のいずれかにマッチしたら, マッチした文字列を消去して, 同じことを繰り返します. そして最後まで達したら True, マッチしなかったら False を返します.

1

s = "dream dreamer erase eraser".split()

def match_string(str):
  """ str の先頭からの文字列が s に含まれるか判定する
  """
  global s
  result = []

  # s が空文字列なら True
  if len(str) == 0:
    return True

  # str の先頭からの文字列が s に含まれるかどうか判定する
  for i in range(len(s)):
    if str.startswith(s[i]):
      result.append(match_string(str.replace(s[i], "", 1)))
    else:
      result.append(False)

  return any(result)

# メイン
line = input().strip()
if match_string(line):
  print("YES")
else:
  print("NO")

結果は, 正解も出ましたが, ほとんどは実行時エラーでした.

マッチした結果をリストに入れていく

そこで, 再帰を使わない方法を考えました. dream, dreamer, erase, eraser のいずれかがマッチしたら, マッチした部分を消去した文字列をリストに加えて, 次以降のループで評価します. そして完全にマッチする結果が出たら True, そうじゃなかったら False を返します.

2

s = "dream dreamer erase eraser".split()
line = input().strip()

def match_string():
  """ line の文字列が s に含まれるかどうか判定する
  """
  global s, line
  result = [line] # リストを作る

  while len(result) > 0: # リストが空でないうちは繰り返す
    str = result.pop(0) # 先頭を取得
    for i in range(len(s)): # 文字列が等しければ, return True
      if str == s[i]:
        return True
      elif str.startswith(s[i]): # 先頭の文字列が等しければ, リストに appepnd し, 次のループへ
        result.append(str[len(s[i]):])
  return False

# メイン
if match_string():
  print("YES")
else:
  print("NO")

これで OK となりました.

さいごに

競プロをがっつりやる時間はないのですが, 勉強として少しずつトライしていこうと思います.