正则表达式匹配问题（带字符类和量词）

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

• '.' 匹配任意单个字符
• '*' 匹配零个或多个前面的元素
• '[abc]' 匹配字符a、b或c中的任意一个（字符类）
• '{m,n}' 匹配前面元素至少m次，至多n次（量词）

需要实现完全匹配，即整个字符串s必须完全匹配模式p。

解题过程

1. 问题分析
这是一个复杂的模式匹配问题，需要处理多种特殊字符。传统的区间DP可以处理'.'和'*'，但加入字符类和量词后需要更精细的状态设计。

2. 状态定义
定义dp[i][j]表示s的前i个字符是否匹配p的前j个字符。

3. 基础情况

• dp[0][0] = true（空字符串匹配空模式）
• 处理p开头的号情况：如果p以"x"开头，可能匹配空字符串

4. 状态转移方程

情况1：普通字符匹配
如果p[j-1]是普通字符且不等于'*'，则：
dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1])

情况2：'.'匹配
如果p[j-1] == '.'，则匹配任意字符：
dp[i][j] = dp[i-1][j-1]

情况3：'*'匹配（处理零次或多次）
如果p[j-1] == '*'，需要检查前一个字符p[j-2]：

• 匹配零次：dp[i][j] = dp[i][j-2]
• 匹配一次或多次：dp[i][j] = dp[i-1][j] && (s[i-1]匹配p[j-2])

情况4：字符类匹配
如果p[j-1] == ']'，向前找到匹配的'['，提取字符类：

• 检查s[i-1]是否在字符类中
• dp[i][j] = dp[i-1][k] && (s[i-1]在字符类中)，其中k是'['的位置

情况5：量词匹配
如果p[j-1] == '}'，向前找到匹配的'{'，提取m,n：

• 需要回溯检查前面m到n个字符是否匹配量词前的模式

5. 算法实现细节

预处理模式字符串

def preprocess_pattern(p):
    # 将字符类和量词转换为更易处理的形式
    tokens = []
    i = 0
    while i < len(p):
        if p[i] == '[':
            j = i + 1
            while j < len(p) and p[j] != ']':
                j += 1
            tokens.append(('char_class', p[i+1:j]))
            i = j + 1
        elif p[i] == '{':
            j = i + 1
            while j < len(p) and p[j] != '}':
                j += 1
            range_str = p[i+1:j]
            m, n = map(int, range_str.split(','))
            tokens.append(('quantifier', m, n))
            i = j + 1
        else:
            tokens.append(('char', p[i]))
            i += 1
    return tokens

动态规划实现

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] == '*' and dp[0][j-2]:
            dp[0][j] = True
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j-1] == '.':
                dp[i][j] = dp[i-1][j-1]
            elif p[j-1] == '*':
                # 匹配零次
                dp[i][j] = dp[i][j-2]
                # 匹配一次或多次
                if p[j-2] == '.' or p[j-2] == s[i-1]:
                    dp[i][j] = dp[i][j] or dp[i-1][j]
            elif p[j-1] == ']':
                # 处理字符类
                k = j - 2
                while k >= 0 and p[k] != '[':
                    k -= 1
                char_class = p[k+1:j-1]
                if s[i-1] in char_class:
                    dp[i][j] = dp[i-1][k]
            elif j < n and p[j] == '{':
                # 处理量词（需要更复杂的处理）
                pass
            else:
                dp[i][j] = dp[i-1][j-1] and s[i-1] == p[j-1]
    
    return dp[m][n]

6. 复杂度分析

• 时间复杂度：O(m × n)，其中m是字符串长度，n是模式长度
• 空间复杂度：O(m × n)，可以优化到O(n)

7. 示例验证

例1：s = "aab", p = "cab"

• 匹配过程：c匹配空，a匹配"aa"，b匹配"b"
• 结果：true

例2：s = "abc", p = "a[bc]d"

• 字符类[bc]匹配'b'
• 结果：false（长度不匹配）

这个解法展示了如何通过区间DP处理复杂的正则表达式匹配问题，关键在于合理设计状态转移方程来处理各种特殊字符。