区间动态规划例题：正则表达式匹配问题（'.'和'*'匹配）

题目描述：
给定一个字符串s和一个模式串p，实现支持'.'和'*'的正则表达式匹配。

• '.' 匹配任意单个字符
• '*' 匹配零个或多个前面的那一个元素
  匹配应该覆盖整个字符串s，而不是部分字符串。

示例：
输入：s = "aa", p = "a" → 输出：false
输入：s = "aa", p = "a*" → 输出：true
输入：s = "ab", p = ".*" → 输出：true

解题思路：
我们使用动态规划，定义dp[i][j]表示s的前i个字符和p的前j个字符是否匹配。

步骤1：初始化

• dp[0][0] = true：两个空字符串匹配
• 处理模式串p开头可能出现a的情况：对于p中连续的x可以匹配空字符串

步骤2：状态转移
考虑两种情况：

1. 当p[j-1]不是'*'时：

   • 如果s[i-1] == p[j-1]或p[j-1] == '.'，则dp[i][j] = dp[i-1][j-1]
   • 否则不匹配

2. 当p[j-1]是'*'时（此时j≥2）：

   • 情况1：''匹配0次前面的字符，即忽略x：dp[i][j] = dp[i][j-2]
   • 情况2：'*'匹配1次或多次前面的字符：
     • 如果s[i-1] == p[j-2]或p[j-2] == '.'，则dp[i][j] = dp[i-1][j]
     • 否则只能匹配0次

步骤3：完整算法

def isMatch(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    
    # 初始化
    dp[0][0] = True
    for j in range(2, 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] == '*':
                # 匹配0次
                dp[i][j] = dp[i][j-2]
                # 匹配1次或多次
                if p[j-2] == '.' or p[j-2] == s[i-1]:
                    dp[i][j] = dp[i][j] or dp[i-1][j]
            else:
                if p[j-1] == '.' or p[j-1] == s[i-1]:
                    dp[i][j] = dp[i-1][j-1]
    
    return dp[m][n]

时间复杂度：O(m×n)，空间复杂度：O(m×n)

这个解法通过动态规划逐个字符比较，正确处理了'.'和'*'的特殊匹配规则，是正则表达式匹配问题的经典解法。