正则表达式匹配涉及到两个字符串的匹配问题，类似于寻找最大公共子串，可使用动态规划思想解决。重点和难点在于如何构建正确的状态转移方程。
示例：
图1 正则表达式匹配输入输出
代码：
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 2]
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == s[i - 1] or p[j - 1] == '.':
dp[i][j] = dp[i - 1][j - 1]
elif p[j - 1] == '*':
if p[j - 2] != s[i - 1] and p[j - 2] != '.':
dp[i][j] = dp[i][j - 2]
else:
dp[i][j] = dp[i - 1][j] or dp[i][j - 2]
return dp[m][n] 解释：
1）dp是一个储存是否可以匹配的状态矩阵，大小为(m + 1)*(n + 1)，其中首行首列分别表示字符串s为空和字符串p为空的情况。其中dp[0][0]代表s，p两者均为空，显然能匹配。对于s为空而p不为空的情况(即对应dp的首行dp[0][j])是否能匹配取决于p中的字符，若为‘*’则可消除前一个字符使其为空，匹配成功。反之若不为‘*’，则无法匹配成功。故此需要初始化首行：
(ps：状态转移矩阵dp大小为(m + 1)*(n + 1)，首行首列代表字符串为空的情况，故dp[i][j]对应s[i-1]和p[j-1])。
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 2]
2）状态转移主要是判断p中的字符：
若其为a-z的小写字母或字符‘.’，则直接与s中对应位置比较即可，若相同则dp[i][j] == dp[i - 1][j - 1]，这里需要注意字符‘.’可匹配任意字符，可归为p[i][j]==s[i][i]这类情况。
if p[j - 1] == s[i - 1] or p[j - 1] == '.':
dp[i][j] = dp[i - 1][j - 1]
若为字符‘*’，则需要考虑两种情况：
1.字符'*'消除前一个字符，即p[j - 1] * 整体为空。出现此类情况是因为我们不想选择p[j - 1]，即p[j - 1]与对应位置的s[i - 1]不相等(需要注意的是这里的p[j - 1]不等于s[i - 1]包含两种情况，一是两者均为小写字母且不等，二是p[j - 1]不为‘.’)
2.字符‘*’复制一次前一个字符，即p[j - 1] *=p[j - 1]p[j - 1]。出现此种情况是因为p[j - 1]与对应位置的s[i - 1]相等。
3.字符‘*’复制k次前一个字符，即p[j - 1] *=p[j - 1]...p[j - 1] (共k次)。出现此种情况是因为p[j - 1]与对应位置的s[i - k + 1]相等。
elif p[j - 1] == '*':
if p[j - 2] != s[i - 1] and p[j - 2] != '.':
dp[i][j] = dp[i][j - 2]
else:
dp[i][j] = dp[i - 1][j] or dp[i][j - 2]
3）需要注意字符‘*’复制k次的情况，这里的k可以为0：
dp[i][j] = dp[i - 1][j] or dp[i][j - 2]
另求助以下代码超时，大家能否帮笔者检查修改：
class Solution:
def isMatch(self, s: str, p: str) -> bool:
def dfs(i, j):
if i >= len(s) and j >= len(p):
return True
if j >= len(p):
return False
match = i < len(s) and (s[i] == p[j] or p[j] == '.')
if (j + 1) < len(p) and p[j + 1] == '*':
return (dfs(i, j + 2) or (match and dfs(i + 1, j)))
if match:
return dfs(i + 1, j + 1)
return False
return dfs(0, 0)
附上同样运用动态规划的最长公共子序列以及编辑距离的代码实现：
LeetCode in Python 300. Longest Increasing Subsequence (最长递增子序列)-CSDN博客
