Участник:Kozub/GAME2

Материал из DISCOPAL
Перейти к: навигация, поиск

Ссылка на задачу на spojcode: https://www.spoj.com/problems/AUTOMATA/

def game2(word, lang):
    if len(word) == 0:
        if set(lang).issubset({'?', '*'}):
            return True
        else:
            return False
    elif len(lang) == 0:
        return False
 
    if lang[0] not in ['?', '*']:
        if lang[0] != word[0]:
            return False
        else:
            return game2(word[1:], lang[1:])
 
    elif lang[0]== '?':
        return game2(word[1:], lang[1:]) or game2(word, lang[1:])
 
    elif lang[0]=='*':
        while len(lang) > 1 and lang[1] in ['?', '*']:
            lang = lang[0] + lang[2:]
 
        if len(lang) == 1:
            return True
        else:
            ind = word.find(lang[1])
            while ind >= 0:
 
                word=word[ind+1:]
                if game2(word, lang[2:]):
                    return True
                ind = word.find(lang[1])
 
            return False
 
n = int(input())
for i in range(n):
    lang = input()
    word = input()
    print('Yes' if game2(word, lang) else 'No' )