10. 正则表达式匹配
Table of Contents
分析 #
对于p中的字符, 可能出现3种情况: 小写字母, ‘.’, ‘*’
由于"*“可以匹配0个或者多个字符, 所以对于p中的某一个子串, 在s中可能有多个匹配的子串. 例如"a*b” 和 “b”, “ab”, “aab"都匹配.
因此, 需要将可能的匹配结果都记录下来. 我们在p中从前往后匹配, 并记录p中的前i个字符在s中的匹配情况.
我们用二维数组dp来记录匹配情况, dp[i][j]如果是True, 则表示字符p[:i+1]和s[:j+1]匹配.
为了方便, 我们先记录空字符串和空字符串的匹配情况. 因此dp的第一维长度是len(p)+1 , 第二维长度是len(s)+1. 由于空字符串和空字符串是可以匹配的, 所以dp[0][0]为True.
由于dp在每一维都增加了1, 因此对于dp[i][j], 与之匹配的字符是p[i-1] 和s[j-1]
class Solution:
def isMatch(self, s: str, p: str) -> bool:
ns = len(s)
np = len(p)
dp = [[False for _ in range(ns+1)]for _ in range(np+1)]
dp[0][0] = True
情况1: “.” #
现在,根据p中出现的字符串来进行相应的判断.
如果p[i-1] 是’.’, 那么可以看p[:i-1]和哪些字符串匹配. p[:i-1]的匹配情况保存在dp[i-1]中, 通过遍历发现了所有的匹配字符串, p[i-1]只需与后一个字符匹配即可.
i = j = 0
for i in range(1, np+1):
if p[i-1] == ".": #能够跟在前一个字符匹配的后面
for j in range(ns):
if dp[i-1][j]:
dp[i][j+1] = True
情况2: “*” #
如果p[i-1] 是’*’, 表达的是p[i-2]出现0次或者多次. 因此我们需要看p[:i-3]的匹配情况, 然后让p[i-2]和p[:i-3]匹配成功的字符串后面的字符进行匹配.p[:i-3]的匹配情况保存在dp[i-2]中, 我们对其进行遍历.
dp[i-2][j]表示p[:i-1]和s[j+1]匹配, 由于’*‘可以匹配0个字符, 因此p[:i+2]也和s[j+1]匹配, 所以dp[i][j] = True.
如果’*’ 之前出现的是’.’ , 那么就可以匹配任意多个的任意字符
如果’*‘之前出现的是普通的小写字母, 那就需要这个字符重复的出现
elif p[i-1] == "*":
for j in range(ns+1):
if dp[i-2][j]:
dp[i][j] = True # 匹配0个
pre = p[i-2]
if pre == ".": # 如果前一个是'.' 那么就可以匹配任意多的任意字符
for k in range(j+1, ns+1):
dp[i][k] = True
else:
for k in range(j+1, ns+1):
if s[k-1] == pre: # *号必须重复之前的字符
dp[i][k] = True
else:
break
情况3: 普通字母 #
如果p[i-1]是普通的字母, 正常匹配即可
else:
for j in range(ns):
if dp[i-1][j] and p[i-1] == s[j]:
dp[i][j+1] = True
由于问题是在问p能否和s匹配, 也就是p[: len(p)+1]和s[:len(s)+1]是否匹配. 因此答案就是dp[len(p)][len(s)]也就是dp[-1][-1].