String constructible from short list of words? AtCoder ABC049C - Daydream [closed]

I am practicing python, and in order to brush up my skill, I am trying the programming contest site AtCoder's past problems.

Daydream

Basically, you are given an input string and have to output YES if the string is constructed with choices of 4 different words ('dream', 'dreamer', 'erase', 'eraser'), otherwise NO.

I implemented as following.

I am aware that there are much better solutions out there, but mine also should work. However, even though first 3 cases were accepted as answers, but other 15 cases fails, and I cannot figure out why my code could fail.

ddee = ('dream', 'dreamer', 'erase', 'eraser')

def match_and_move(s, t, i):
"""checks if string s starts with any of the 4 choices starting from index i"""
if s == t:
return True
for word in ddee:
if s.startswith(word, i):
if match_and_move(s, t+word, i+len(word)):
return True
return False

S = input()
T = ''
print('YES' if match_and_move(S, T, 0) else 'NO')


What am I doing wrong here?

Any assistance would be appreciated.

EDIT :

Because this is programming contest site, I was not provided with the input file for the all 18 tests.
I just know that first 3 tests were marked 'AC - Accepted' and other 15 tests were marked 'RE - Runtime Error' without actual error being displayed.
I performed test on my own based on the requirements (as well as the example provided by them on the question page).
At least I know that this code is working as they intended even if it is partially.

Further testing my code, I was looking further in to the constraints.

• 1≦|S|≦10^5
• s consists of lowercase English letters.

I prepared a string that is 7000 characters long 'dreamerdreamer...dreamer' which should return 'YES' as this is just a repeat of 'dreamer' which is one of the 4 phrases.

RecursionError: maximum recursion depth exceeded in comparison

Which is self explanatory. (and is also something @VincentRG has suggested)

import sys
sys.setrecursionlimit(10**6)


By adding above, on my PC this program is working with this large input. 5 more problems are solved on the website, and 10 of the website's test were returning Memory Limit Exception, which also make sense.

• I have edited my post. I do know that the code is working as I intend it to work. I am only provided with limited error report 15 cases that failed Feb 2 '20 at 17:43
• Thank you very much greybeard for your edit. It is much clearer than how I was writing! Feb 2 '20 at 19:42

It seems to be fine. What are the failing cases' inputs? Following your link I only see 3 cases which should indeed work.

However, I see there's a limitation of time and memory usage at the beginning, and that S max length is 100000. Your code might for example exceed maximum recursion depth. I think a simpler solution would be to use regex. For example (and I added a long sample):

import re
import random

regexPattern = "^(dream(er)?|eraser?)*\$"
sampleList = [
"erasedream",
"dreameraser",
"dreamerer"]

# just add a looooooong sample
longSample = ""
mandatoryWords = ["dream", "dreamer", "erase", "eraser"]
while True:

if len(longSample) + len(addWord) > 100000:
break
else:

sampleList.append(longSample)

for sample in sampleList:
match = re.fullmatch(regexPattern, sample)

if match != None:
print("YES")
else:
print("NO")


outputs

YES
YES
NO
YES

• Thank you very much for your answer. Unfortunately, I guess due to the fact that it is programming contest, I do not get to see the solution's input file :(. Feb 2 '20 at 8:29