Занимательный пролог #3

Не без этого…

Занимательный пролог #3

Нашел решение с использованием регулярных выражений, но в комбинации с разбиением исходного выражения по `*` и отсечением исходной строки по каждому из них.

class Solution:
    start_p = re.compile("\*+")
    q_p = re.compile("\?")

    def isMatch(self, s: str, p: str):
        test_s = s
        pattern_list = list(filter(None, self.pat_format(p).replace('.*?', '\n.*?').split('\n')))
        pattern_len = len(pattern_list)
        last_index = pattern_len - 1

        for index, pattern in enumerate(pattern_list):
            if index == last_index:
                pattern = pattern + '$'

            m = re.match(pattern, test_s)
            if not m:
                return False

            test_s = test_s[m.span()[1]:]

        return not bool(test_s)

    def pat_format(self, pat: str):
        pat = self.q_p.sub(".", pat)
        pat = self.start_p.sub(".*?", pat)
        return pat

Вроде получился неплохой результат, лучший прогон: 108 Runtime (ms).
Your runtime beats 87.06 % of python3 submissions.

Занимательный пролог #3

При использовании регулярных выражений из стандартной библиотеки, к сожалению, действительно долго. На этом выражении запнулся на ~5 минутах.
Но при использовании пакета regex, скорость выполнения ~0.066 сек. Но, как я понял, его нельзя импортировать.
Прошу прощения, это ответ на этот комментарий.

Занимательный пролог #3

Поправка, нашел весь текст в исходном коде.
Просто не отображается вся строка в тексте комментария по длине.

Занимательный пролог #3

Приведенная строка — это полный текст поиска?
В нем нет сочетания такого большого количества `aaaaaaaaa` (хотя и не в нем наверно суть) и нет финишной кавычки.
Дополнительный вопрос: данные в группировках нужны? Они замедляют работу в ~2.5 раза.

Можно заменить:

def pat_format(pat):
    pat = re.sub("\*{2,}", "*", pat)
    pat = re.sub("\?", ".", pat)
    pat = re.sub("\*", ".*", pat)
    return pat

Занимательный пролог #3

import re
import time

def isMatch(s, p):
    m = re.match(pat_format(p), s)
    if not m:
        return False
    else:
        return m.group() == s


def pat_format(pat):
    pat = re.sub("[*]{2,}", "*", pat)
    pat = re.sub("[?]", ".", pat)
    pat = re.sub("[*]", "(.)*", pat)
    return pat


pt=time.time()
print(isMatch("aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba","*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*"))
print(time.time()-pt)