通配符匹配 DP 内存溢出问题

动态规划（DP）是解决通配符匹配问题的常用方法，但传统二维 DP 表在处理大数据量时会因内存占用过高而溢出。以下是优化方案：

空间优化：滚动数组

传统 DP 表需存储整个 dp[m][n] 矩阵（m 和 n 为字符串长度），空间复杂度为 $O(mn)$。改用滚动数组可将空间降至 $O(n)$：

def isMatch(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp_prev = [False] * (n + 1)
    dp_prev[0] = True
    
    for j in range(1, n + 1):
        if p[j - 1] == '*':
            dp_prev[j] = dp_prev[j - 1]
    
    for i in range(1, m + 1):
        dp_curr = [False] * (n + 1)
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp_curr[j] = dp_curr[j - 1] or dp_prev[j]
            elif p[j - 1] == '?' or p[j - 1] == s[i - 1]:
                dp_curr[j] = dp_prev[j - 1]
        dp_prev = dp_curr
    
    return dp_prev[n]

贪心算法优化

针对 * 匹配场景，贪心算法可避免存储整个 DP 状态：

def isMatch(s: str, p: str) -> bool:
    i = j = 0
    star_i = star_j = -1
    
    while i < len(s):
        if j < len(p) and (p[j] == '?' or p[j] == s[i]):
            i += 1
            j += 1
        elif j < len(p) and p[j] == '*':
            star_i, star_j = i, j
            j += 1
        elif star_j != -1:
            i, j = star_i + 1, star_j + 1
            star_i += 1
        else:
            return False
    
    while j < len(p) and p[j] == '*':
        j += 1
    
    return j == len(p)

分治策略

将大字符串分割为子段处理，减少单次 DP 计算规模：

1. 按固定长度切分输入字符串 s 和模式 p。
2. 对每个子段应用 DP 或贪心算法。
3. 合并子段结果时处理边界条件（如跨段的 * 匹配）。

位运算优化

利用位掩码压缩 DP 状态存储，适用于特定场景：

def isMatch(s: str, p: str) -> bool:
    bitmask = 1
    for c in s:
        next_mask = 0
        for i in range(len(p)):
            if (bitmask >> i) & 1:
                if p[i] == '*' or p[i] == '?' or p[i] == c:
                    next_mask |= 1 << (i + 1)
        bitmask = next_mask
    return (bitmask >> len(p)) & 1 == 1

预处理与剪枝

1. 合并连续的 * 为单个 *，减少冗余计算。
2. 提前判断固定字符是否匹配，快速返回 False。
3. 对模式 p 进行分段，跳过不可能匹配的子模式。