String constructible from short list of words? AtCoder ABC049C - Daydream 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.

Thank you in advanced.

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.

EDIT 2 / Answer :

Since this question is closed, I cannot place a separate answer. 

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.

And I received following error.

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.
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:
    addWord = mandatoryWords[random.randint(0, 3)]

    if len(longSample) + len(addWord) &gt; 100000:
        break
    else:
        longSample += addWord

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