LeetCode通配符匹配递归加记忆化超时且测试用例通过数减少问题

核心问题：记忆化逻辑不完整+递归与循环混合导致的效率低下 #

你的代码添加记忆化后性能反而下降，核心原因是记忆化覆盖范围不全，仅在遇到*时的部分分支尝试缓存，而大量中间状态、终止条件的结果都没有存入记忆数组；同时递归与循环混合的写法导致逻辑混乱，重复计算无法避免，额外的记忆化判断反而增加了开销。

具体问题点 #

1. 记忆化未覆盖所有状态：只有遇到*后的递归分支才检查memo，而逐个字符匹配的过程、终止条件的返回结果都没有存入memo，导致相同状态反复计算。
2. 递归与循环混合逻辑混乱：第一个for循环直接递增索引跳过匹配过程，这些中间状态完全没有被记忆化，回溯时需要重复走流程。
3. memo判断逻辑不全：仅处理了memo为1和-1的情况，忽略了memo为0的缓存结果，同时当前递归状态的结果也没有存入memo。

修复后的代码 #

思路说明 #

• 预处理模式串：将连续的*替换为单个*，减少递归分支。
• 纯递归+全状态记忆化：每个(sIdx, pIdx)状态都先检查memo，计算后立即存入缓存，彻底避免重复计算。

#include <stdlib.h>
#include <string.h>

int memo[2001][2001]; // 覆盖s和p长度最大2000的情况

// 预处理模式串，去掉连续的*
char* simplifyPattern(char* p) {
    int len = strlen(p);
    char* newP = malloc(len + 1);
    int idx = 0;
    for (int i = 0; i < len; i++) {
        if (p[i] == '*') {
            newP[idx++] = '*';
            // 跳过后续连续的*
            while (i + 1 < len && p[i+1] == '*') i++;
        } else {
            newP[idx++] = p[i];
        }
    }
    newP[idx] = '\0';
    return newP;
}

int check(char* s, char* p, int sIdx, int pIdx) {
    // 先检查记忆化缓存，避免重复计算
    if (memo[sIdx][pIdx] != -1) {
        return memo[sIdx][pIdx];
    }

    int res;
    // 终止条件处理
    if (s[sIdx] == '\0' && p[pIdx] == '\0') {
        res = 1;
    } else if (s[sIdx] == '\0') {
        // 模式串剩余部分只能是*（已预处理，所以只需递归跳过*）
        res = (p[pIdx] == '*') ? check(s, p, sIdx, pIdx+1) : 0;
    } else if (p[pIdx] == '\0') {
        res = 0;
    } else if (p[pIdx] == '?' || s[sIdx] == p[pIdx]) {
        // 单个字符匹配，递归下一个位置
        res = check(s, p, sIdx+1, pIdx+1);
    } else if (p[pIdx] == '*') {
        // *两种匹配方式：匹配0个字符（跳过*）或匹配至少一个字符（s前进一位）
        res = check(s, p, sIdx, pIdx+1) || check(s, p, sIdx+1, pIdx);
    } else {
        // 字符不匹配且不是通配符
        res = 0;
    }

    // 将结果存入记忆化缓存
    memo[sIdx][pIdx] = res;
    return res;
}

bool isMatch(char* s, char* p) {
    char* simplifiedP = simplifyPattern(p);
    int sLen = strlen(s);
    int pLen = strlen(simplifiedP);

    // 初始化记忆化数组为-1（未计算状态）
    for (int i = 0; i <= sLen; i++) {
        for (int j = 0; j <= pLen; j++) {
            memo[i][j] = -1;
        }
    }

    bool result = check(s, simplifiedP, 0, 0) == 1;
    free(simplifiedP);
    return result;
}

修复效果 #

修改后所有状态都会被缓存，彻底避免重复计算，同时预处理模式串减少了不必要的递归分支，能高效通过所有测试用例。

内容的提问来源于stack exchange，提问作者Heap_stack_born_hater