Python 算法学习-动态规划-正则表达式
# 给定一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配# '.' 匹配任意单个字符
# '*' 匹配零个或多个前面的那一个元素
def is_match(s: str, p: str):
def matches(i, j):
# 没有字符，匹配失败
if i == 0:
return False
# .匹配任意字符
if p1] == '.':
return True
return s1] == p1]
m, n = len(s), len(p)
# dp: s的前i个字符与p的前j个字符是否能匹配
dp = [[False] * (n + 1) for _ in range(m + 1)]
# base case
# 空白匹配空白
dp[0][0] = True
for i in range(m + 1):
for j in range(1, n + 1):
# 匹配'*'通配符有两种情况:
# 1.要么匹配0次,匹配j前进2位再进行判断
# 2.要么进行匹配，字符i前进1位,再进行匹配
if p1] == '*':
dp |= dp2]# 0次匹配, 跳过
dp |= dp1] and matches(i, j - 1)# 匹配*号前的字符，字符串前进一位
else:
# 判断前个匹配情况和当前匹配情况
dp = dp1]1] and matches(i, j)
return dp
# 测试代码
s = 'aabb'
p = 'a*.b'
print(is_match(s, p))
页:
[1]