Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняСтатья 24 темы LeetCodeВ этой статье давайте рассмотрим 44 вопроса LeetCode - Сопоставление подстановочных знаков, это задача высокой сложности, она будет немного сложной, но хорошая новость заключается в том, что нет алгоритма, который мы не видели раньше.
Смысл вопроса очень прост, учитывая две строки s и p, гдеs — родительская строка, p — строка шаблона. Кратко объясните эти две концепции, которые обычно появляются в задачах сопоставления строк. Некоторые учащиеся могут не очень хорошо это понять. Давайте проведем неуместную аналогию. Мы можем думать о материнской строке как о замке, а о строке шаблона как о ключе. Некоторые мастер-ключи могут открывать несколько замков, а это означает, что ключ можно сменить, а замок зафиксировать. Нам нужно судить, может ли строка шаблона соответствовать материнской строке, то есть может ли ключ открыть замок.
В строке шаблона p может быть два специальных символа, один из которых ?, что означаетсоответствует любому одиночному символу. Другой *, что означаетсоответствует любой строке символов, включая пустую строку. Так что это * выглядит очень мощным, его можно подобрать произвольно. Но в этом вопросе есть ограничение: s и p должны быть полным, а не частичным совпадением. Другими словами, должны использоваться все символы p. Например, строка s — это aab, а строка p — это *c. Хотя * достаточно для соответствия всему содержимому строки s, его нельзя рассматривать как допустимое совпадение, поскольку оно не используется после c.
Чтобы упростить описание, мы используем si для представления i-го символа строки s и pi для представления i-го символа строки p.
поиск
Мы по-прежнему начинаем с простого метода и сначала думаем о насильственном решении.Легко обнаружить, что в этой задаче нет простого и грубого насильственного расчета. Причина также очень проста, потому что когда появляется символ *,Мы не знаем точно, как долго это должно совпадать. Это может быть 0 или любая длина, совпадающая с концом.
Лучший способ исправить это — попробовать все это и перечислить длины, которым * должен соответствовать этот символ. Однако, поскольку количество * может быть больше одного, если их больше одного, потому что передняя и задняя части будут влиять друг на друга, и между передней и задней частью существует порядок, то есть решение о как сопоставить символ * не составляется вместе, а имеет последовательность. Она ставится не вместе с ферзями среди восьми ферзей, а в последовательном порядке.Если рассматривать * как ферзя, то это и в самом деле совершенно очевидно.поисковые вопросы.
Если разобраться, то решить эту задачу как задачу поиска несложно, по сути это простое перечисление.
Мы ищем позицию, где совпадают строки s и p. Мы используем si для представления символа, которому в данный момент должна соответствовать строка s, и pi для представления текущего символа, которому должна соответствовать строка p. Если символ в позиции пи не *, то ситуация относительно ограничена, нам нужно только судить о верхней и нижней границах и о том, совпадают ли они. Если позиция пи равна *, ситуация немного сложнее, потому что появление * подразумевает три вида решений.
Первое решениеНе используйте * для соответствия si в текущей позиции, что в данном случае означает, что мыбросить это*, но si по-прежнему не находит соответствующий объект, поэтому si не может двигаться. С этого момента мы можем получить следующую позицию для перехода: si, pi+1. То есть указатель в p перемещается на один бит, а указатель в s остается на месте, ожидая продолжения сопоставления.
Второе решениесоответствует только текущему si, больше не соответствует тому, что идет после si. В этом случае нам просто нужно рассматривать * как обычный символ, тогда позиция, в которую мы должны перейти, будет si+1, pi+1. Другими словами, указатели в s и p переместились каждый на один бит.
Третье решение*Не только соответствует текущему si, но и продолжает соответствовать вниз, в этом случае нам нужно сохранить положение pi и переместить только si, что означает, что мы будем двигаться к si+1 и pi.
Но если мы внимательно проанализируем его, мы обнаружим, чтоЭти три случая можно объединитьиз. Во втором случае мы сопоставляем только текущую позицию, что фактически эквивалентно выполнению нами третьей стратегии в текущей позиции и стратегии 1 в позиции после переноса.
Например: Например, строка s — это abc, а строка p — это a*c. Когда мы совпадаем со вторым символом, мы выполняем стратегию 3, поэтому мы переходим к 2, 1. То есть si равно c, а pi по-прежнему *. В это время, если мы снова выполним стратегию 1, она перейдет к 2, 2, что согласуется с реализацией стратегии 2 в начале. Таким образом можно сократить и ускорить процесс принятия решений при наличии множества файлов *.
Наконец, поскольку это вопрос о том, существует ответ или нет,не требует от нас поиска всех решений. В этом случае использование bfs было бы более эффективным, чем dfs, но, к сожалению, я попробовал оба метода и не смог пройти, потому что истекло время ожидания. Вероятно, это причина для Python (Интерпретируемые языки неэффективны), потому что я могу обойтись C++.
Хоть и не может пройти, но идея правильная, если не возражаете, можете глянуть код:
class Solution:
def isMatch(self, s: str, p: str) -> bool:
n, m = len(s), len(p)
if m == 1 and p[0] == '*':
return True
import queue
que = queue.Queue()
que.put((0, 0))
while not que.empty():
si, pi = que.get()
if si == n and pi == m:
return True
# 如果s串已经匹配完了，p串还没结束
# 需要特判一下p串当中是否是*
# 如果p串的末尾都是*，那么也是可以匹配的
if si == n:
if p[pi] == '*':
que.put((si, pi + 1))
continue
continue
elif pi >= m:
continue
# 如果没有出现*，那么我们判断能否匹配
elif p[pi] == '?' or p[pi] == s[si]:
que.put((si + 1, pi + 1))
continue
# 否则的话分两种情况往下
elif p[pi] == '*':
que.put((si, pi + 1))
que.put((si+1, pi))
return False
динамическое программирование
Хотя вышеупомянутый метод не может быть передан, он на самом деле дал нам много вдохновения.Если мы объединим упомянутые выше si и piрассматривается как государствоЕсли да, то хотя мы реализовали это с помощью bfs, по сути это идея динамического программирования.
В некоторых задачах динамического программирования мы также поддерживаем состояние через очереди. Мы будем хранить все допустимые состояния в очереди, а когда переходим к новым допустимым состояниям через состояния и решения, продолжаем вставлять в очередь. Так что с этой точки зрения задачи динамического программирования и поиска по сути схожи, а точнееДинамическое программирование — это всего лишь идея, а носитель, который она может реализовать, может быть разным., либо используя рекурсию массива, либо используя структуры данных для сохранения состояния. Это очень важно и лежит в основе нашего расширенного динамического программирования.
Почему мы теряем время?
Если рассматривать идею поиска просто как динамическое программирование, мы обнаружим, что этопродвигатьдинамическое программирование. Чтобы кратко представить, хотя состояние и переход динамического программирования различны в каждом вопросе, есть только две общие идеи.Один называется прямым толчком, другой - обратным толчком..
Забегая вперед, мы записываем все допустимые состояния, а затемИз правового государства передача через принятие решений, и запишите статус, полученный от передачи, для последующей передачи. Если мы соединим эти состояния последовательно, мы обнаружим, что выполняем в логическом порядке, поэтому это называется продвижение вперед. Обратный вывод как раз наоборот, мы пересекаем неизвестное состояние,Исследуйте его источник через отношения перехода между состояниями, тем самым определяя результат текущего неизвестного состояния. Другими словами, один — от известного к неизвестному, а другой — сначала получить неизвестное, а затем исследовать его известные источники.
Почему нельзя выдвигать это в этом вопросе? Потому что, когда * появляется, * все еще находится в состоянии, которое мы продолжаем нажимать. Например, когда мы решаем использовать * для соответствия si, мы переходим в состояние si+1, pi. В состоянии после заказа он также содержит * и будет сталкиваться с другими состояниями.Многие из этих состояний пересекаются, и многие из этих перекрывающихся состояний не могут быть разрешены путем обрезки, например ряд * в p-строке. В это время мы можем подумать об обратном толчке под другим углом.
В обычной процедуре мы используем dp[i][j] для записи совпадающего состояния s[:i+1] и p[:j+1], а затем какие состояния могут быть переданы этому dp[i][j] от? На самом деле он очень ограничен: если si и pi могут совпадать, то его можно передать из dp[i-1][j-1]. Если это не совпадает, нам нужно проверить, является ли число пи *. Если да, то возможны два случая: первый означает, что * соответствует пустому, а si передается pi-1, поэтому его можно передать из dp[i][j-1]. Другой должен соответствовать si.Поскольку * может соответствовать более чем одному числу, он может быть передан из dp[i-1][j] в это время.Поскольку каждый i,j имеет очень ограниченный источник состояний, существует только ограниченное число состояний., так что мы можем перечислить все i, j и вернуться назад.Эта сложность составляет O (nm), что полностью управляемо.
Если в приведенном выше абзаце разобраться ясно, это очень очевидная проблема динамического программирования.
Давайте посмотрим на код и получим больше деталей из кода.
class Solution:
def isMatch(self, s: str, p: str) -> bool:
n, m = len(s), len(p)
if m == 1 and p[0] == '*':
return True
s = ' ' + s
p = ' ' + p
# 注意下标，第一个range里的是列数，第二个range里的是行数
# 申请一个dp[n][m]的数组
dp = [[False for _ in range(m+2)] for _ in range(n+2)]
dp[0][0] = True
# i从0开始，因为p的开头出现*可以匹配空串
for i in range(0, n+1):
for j in range(1, m+1):
# si和pj匹配
if s[i] == p[j] or p[j] == '?':
dp[i][j] = dp[i-1][j-1] if i > 0 else False
continue
# pj出现*，这时候判断上游能否有合法的转移
if p[j] == '*':
dp[i][j] = (dp[i-1][j] if i > 0 else False) | dp[i][j-1]
return dp[n][m]
Этот код короткий, ноЕсть много деталей, включая индексы и граничные условия.. Поэтому рекомендуется понять идею и написать ее от руки, а потом уже думать о коде, думаю, выигрыша будет больше. Поскольку многие детали можно понять, увидев неправильный случай и подумав, это также хороший момент в LeetCode, вы можете видеть тестовые данные, вы можете знать, где вы ошибаетесь.
Это все, что касается сегодняшней статьи. Кроме того, во второй статье я делюсь использованием плагина LeetCode в vscode. Заинтересованные студенты не должны пропустить его. Наконец, я желаю всем вам приятного письма.
Если вы чувствуете, что что-то приобрели, пожалуйста, нажмитеПодпишитесь или сделайте ретвитЧто ж, твое маленькое усилие много значит для меня.