Нашел решение с использованием регулярных выражений, но в комбинации с разбиением исходного выражения по `*` и отсечением исходной строки по каждому из них.
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.
При использовании регулярных выражений из стандартной библиотеки, к сожалению, действительно долго. На этом выражении запнулся на ~5 минутах.
Но при использовании пакета regex, скорость выполнения ~0.066 сек. Но, как я понял, его нельзя импортировать.
Прошу прощения, это ответ на этот комментарий.
Приведенная строка — это полный текст поиска?
В нем нет сочетания такого большого количества `aaaaaaaaa` (хотя и не в нем наверно суть) и нет финишной кавычки.
Дополнительный вопрос: данные в группировках нужны? Они замедляют работу в ~2.5 раза.
Можно заменить:
def pat_format(pat):
pat = re.sub("\*{2,}", "*", pat)
pat = re.sub("\?", ".", pat)
pat = re.sub("\*", ".*", pat)
return pat
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)
Вроде получился неплохой результат, лучший прогон: 108 Runtime (ms).
Your runtime beats 87.06 % of python3 submissions.
Но при использовании пакета regex, скорость выполнения ~0.066 сек. Но, как я понял, его нельзя импортировать.
Прошу прощения, это ответ на этот комментарий.
Просто не отображается вся строка в тексте комментария по длине.
В нем нет сочетания такого большого количества `aaaaaaaaa` (хотя и не в нем наверно суть) и нет финишной кавычки.
Дополнительный вопрос: данные в группировках нужны? Они замедляют работу в ~2.5 раза.
Можно заменить: