正则表达式匹配
给你一个字符串s和一个字符规律p,请你来实现一个支持'.'和'*'的正则表达式匹配
- '.'匹配任意单个字符
- '*'匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串s的,而不是部分字符串
示例1
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串
示例2
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次
示例3
输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）
提示
- 1 <= s.length <= 20
- 1 <= p.length <= 20
- s只包含从a-z的小写字母
- p只包含从a-z的小写字母,以及字符.和*
- 保证每次出现字符*时，前面都匹配到有效的字符
题解
- 状态定义:
dp[i][j]表示s的前i个字符和p的前j个字符能否匹配 - 状态转移:
dp[0][0]代表的是空字符的状态,因此dp[i][j]对应的字符s[i-1]和p[j-1]- 当
p[j-1] != '*'时: $$ dp[i][j] = \begin{cases} dp[i-1][j-1], s[i]=p[j] \ False, s[i] \neq p[j] \end{cases} $$ - 当
p[j-1] = '.'时:dp[i][j] = dp[i-1][j-1] - 当
p[j-1] == '*'时, 表示可对p[j]的前一个字符p[j−1]匹配(或理解为复制)任意次(包括0次)- 匹配零次:
dp[i][j] = dp[i][j-2] - 匹配一次: 若
s[i]=p[j-1],则dp[i][j]可由dp[i-1][j-2]转移而来,此时有:dp[i][j] = dp[i-1][j-2] && s[i]=p[j-1] - 匹配
k次: 若s[i-k+1,...,i]=p[j-1],则有:dp[i][j] = dp[i-k][j-2] && s[i-k+1,...,i]=p[j-]
- 匹配零次:
- 当
- 转移方程: $$ dp[i][j] = \begin{cases} dp[i-1][j-1], s[i]=p[j] 或 p[j]='.' \ dp[i][j-2], p[j]='' \ dp[i][j-2] 或 dp[i-1][j], p[j]=''且(s[i]=p[j-1]或p[j-1]='.') \end{cases} $$
- 方程初始化:
dp[0][0]=True- 对于其他
dp[0][j]p[j]='*'时,则有dp[0][j]=dp[0][j−2]- 反之.
s[0,...,j]无法与空字符匹配,因此有dp[0][j]=False
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s) + 1, len(p) + 1
# 为便于状态更新,减少对边界的判断,初始二维dp数组维度为(m+1)×(n+1)
# 其中第一行和第一列的状态分别表示字符串s和p为空时的情况。
dp = [[False] * n for _ in range(m)]
dp[0][0] = True # 标识两个空字符串能够匹配
for j in range(1, n):
if p[j-1] == '*':
dp[0][j] = dp[0][j-2]
for i in range(1, m):
for j in range(1, n):
if s[i-1] == p[j-1] or p[j-1] == '.':
dp[i][j] = dp[i-1][j-1]
elif p[j-1] == '*': # 首字符不为*,则此处j>=2
dp[i][j] = dp[i][j-2] # *号复制前面字符零次
if s[i-1] == p[j-2] or p[j-2] == '.': # *号复制前面字符k(k>0)次
dp[i][j] |= dp[i-1][j]
return dp[-1][-1]