Динамическое программирование — это алгоритмическая парадигма решения задач, ориентированная на распознавание и устранение повторяющихся вычислений. Ранее на этой неделе у меня была еще одна статья, посвященная динамическому программированию, и перспектива, которую я нашел полезной. Я оставляю ссылку на это ниже.
Во второй статье я сосредоточусь на другом примере — сопоставлении подстановочных знаков.
Постановка задачи
Имея входную строку (s) и шаблон (p), реализуйте сопоставление шаблонов с подстановочными знаками с поддержкой '?' и '*', где:
'?'Соответствует любому одиночному символу.'*'Соответствует любой последовательности символов (включая пустую последовательность).
Сопоставление должно охватывать всю входную строку (не частично).
Решение
Опять же, мы должны начать с небольших примеров.
isMatch(“”, “”) = True =› Пустой шаблон соответствует пустой строке.
isMatch(“”, “a”)= False =› Образец буквы не может соответствовать пустой строке.
isMatch(“”, “?”)= False =› Один шаблон сопоставления не может соответствовать пустой строке.
isMatch(“”, “*”)= True =› Шаблон сопоставления подстановочных знаков может соответствовать пустой строке.
isMatch("a", "")= False =› Пустой шаблон не может соответствовать непустой строке.
Итак, мы фактически закончили с небольшими примерами. Как я покажу вам через минуту, мы можем свести любой паттерн к этим паттернам, распознав набор простых отношений.
isMatch("a__", "a__") или isMatch("a__", "?__")= isMatch("__", "__") =› Когда шаблон букв или одно совпадение соответствует первому символу строки, мы можем использовать оба символа и управлять остальными S и P.
Это последнее - реальная сделка. Что происходит, когда мы встречаем подстановочный знак?
isMatch("a__", "*__") имеет 3 возможности.
- «*» соответствует ровно одному символу. Итак, оба персонажа съедены.
isMatch("a__", "*__") = isMatch("__", "__")
2. «*» соответствует нулю символов. Таким образом, потребляется только «*».
isMatch("a__", "*__") = isMatch("a__", "__")
3. «*» соответствует одному или нескольким символам. Таким образом, потребляется только «а».
isMatch("a__", "*__") = isMatch("__", "*__")
Ставим визуальное представление.
Ниже представлено дерево соответствия для «aaa» и «*?a».
Соответственно, ниже приведены деревья сопоставления для этих 3 дочерних узлов.
Теперь вы должны понять, что я начал раскрашивать узлы, которые появляются более одного раза, разными цветами. Итак, даже на этом втором шаге у нас есть повторяющийся узел, синий isMatch(aa, ?a).
На данный момент визуальное представление позволяет нам прийти к аналогичному выводу даже в пределах этой картины. Каждая «*» приводит к экспоненциальному росту количества вычислительных шагов, так как создает 3 отдельные ветви.
Зеленые узлы — это узлы isMatch («», «»), достижение такого узла означает, что мы действительно достигли совпадения.
Даже в этом небольшом примере с одним узлом «*» мы видим 5 дубликатов. Итак, можем ли мы на самом деле вычислить количество шагов? В общем случае, наверное, нет. Я дам вам цифры для конкретного набора случаев.
Давайте рассмотрим isMatch(a…a, *…*) для разной длины «a» и «*». Ниже я записал два числа: первое — это количество вызовов isMatch(“”, “”), а второе — количество всех вызовов функций для этого запроса.
isMatch(a, *): 2, 5 isMatch(a, **): 4, 11 isMatch(a, ***): 6, 19 isMatch(a, ****): 8, 29 isMatch(a, *****): 10, 41 isMatch(aa, *): 2, 8 isMatch(aa, **): 8, 25 isMatch(aa, ***): 18, 56 isMatch(aa, ****): 32, 105 isMatch(aa, *****): 50, 176 isMatch(aaa, *): 2, 11 isMatch(aaa, **): 12, 45 isMatch(aaa, ***): 38, 127 isMatch(aaa, ****): 88, 289 isMatch(aaa, *****): 170, 571 isMatch(aaaa, *): 2, 14 isMatch(aaaa, **): 16, 71 isMatch(aaaa, ***): 66, 244 isMatch(aaaa, ****): 192, 661 isMatch(aaaa, *****): 450, 1522 isMatch(aaaaa, *): 2, 17 isMatch(aaaaa, **): 20, 103 isMatch(aaaaa, ***): 102, 419 isMatch(aaaaa, ****): 360, 1325 isMatch(aaaaa, *****): 1002, 3509 Some big examples(these do not have the total number) isMatch(aaaaaaaaaa, **********): 4780008 isMatch(aaaaaaaaaa, ***********): 11414898 isMatch(aaaaaaaaaa, ************): 25534368 isMatch(aaaaaaaaaa, *************): 53972178 isMatch(aaaaaaaaaa, **************): 108568488 isMatch(aaaaaaaaaaa, **********): 10377180 isMatch(aaaaaaaaaaa, ***********): 26572086 isMatch(aaaaaaaaaaa, ************): 63521352 isMatch(aaaaaaaaaaa, *************): 143027898 isMatch(aaaaaaaaaaa, **************): 305568564 isMatch(aaaaaaaaaaaa, **********): 21278640 isMatch(aaaaaaaaaaaa, ***********): 58227906 isMatch(aaaaaaaaaaaa, ************): 148321344 isMatch(aaaaaaaaaaaa, *************): 354870594 isMatch(aaaaaaaaaaaa, **************): 803467056 isMatch(aaaaaaaaaaaaa, **********): 41517060 isMatch(aaaaaaaaaaaaa, ***********): 121023606 isMatch(aaaaaaaaaaaaa, ************): 327572856 isMatch(aaaaaaaaaaaaa, *************): 830764794 isMatch(aaaaaaaaaaaaa, **************): 1989102444
Я попытался обнаружить какую-то глубокую функцию, работающую сзади, но не смог найти никаких математических уравнений. Если кто-то, я хотел бы услышать ваши результаты. Но ясно, что длина имеет мультипликативный эффект и быстро становится очень большой.
Конечно, это число само по себе не имеет большого значения, так как isMatch("", "") на самом деле дешевле, чем вызов мемоизации, но я думаю, что оно дает представление о количестве повторяющихся вычислений. Итак, как мы это запоминаем? Я реализовал очень простой кеш в коде ниже.
# Call counter for the measurements in this articc
call_counts = {}
# Call cacher
calls = {}
def isMatch(s: str, p: str) -> bool:
## Caching Parts
# Call counter
if (s, p) in call_counts:
call_counts[(s, p)] += 1
else:
call_counts[(s, p)] = 1
# Memoization
if (s, p) in calls:
return calls[(s, p)]
## Base cases
# When both are consumed, it's a match
if len(s) == 0 and len(p) == 0:
calls[(s, p)] = True
return True
# When pattern is consumed, it's not a match
if len(p) == 0:
calls[(s, p)] = False
return False
# When string is consumed, it's a match if the rest of the pattern is all '*'
if len(s) == 0:
return p[0] == '*' and isMatch(s, p[1:])
## Recursive cases
# Consume both if they match
# a___ <> a___
if s[0] == p[0]:
return isMatch(s[1:], p[1:])
# Consume both if pattern is '?'
# a___ <> ?___
if p[0] == '?':
return isMatch(s[1:], p[1:])
# There are 3 cases for '*'
# a___ <> *___
if p[0] == '*':
# 1. Consume both: so that '*' matches 1 character
c1 = isMatch(s[1:], p[1:])
# 2. Consume string, but not pattern: so that '*' matches 1 or more characters
c2 = isMatch(s[1:], p)
# 3. Consume pattern, but not string: so that '*' matches 0 characters
c3 = isMatch(s, p[1:])
return c1 or c2 or c3
calls[(s, p)] = False
return False
print(isMatch('aa', 'a')) # False
print(isMatch('aa', '*')) # True
print(isMatch('cb', '?a')) # False
print(isMatch('adceb', '*a*b')) # True
print(isMatch('acdcb', 'a*c?b')) # False
print(isMatch('adceb', '*a*b*')) # True
Эта мемоизация несколько хакерская, в том смысле, что вы не сможете скопировать и вставить этот код в leetcode, но ее, безусловно, можно адаптировать. Вместо того, чтобы использовать строки для кеширования, легко использовать индексы, что, в свою очередь, означает, что вам на самом деле не нужна карта, а просто простой массив 2d, который позволяет индексировать O (1) (константа).
Заключение
Мне эта задача нравится больше, чем задача 3sum в первой статье, так как она позволяет гораздо более принципиальный способ запоминания. Тот факт, что 3sum зависел от вызовов 2sum, был немного грубым и, возможно, его было труднее усвоить. Но isMatch, полностью зависящий от самого себя, позволяет гораздо лучше увидеть дерево вызовов. Если у вас есть другие проблемы, которые вы хотите решить в разных статьях, дайте мне знать!
