不知道为什么超过了leetcode的时间限制

Question

问题是https://leetcode.com/problems/wildcard-matching/

我用递归编写了代码，并用记忆优化。 但出现“超出时间限制”的情况。为什么会这样？？

int memo[2000][2000];

int check(char* s, char* p, int sIdx, int pIdx){
    for (;s[sIdx]!=0&&p[pIdx]!=0;sIdx++,pIdx++){
        if (s[sIdx]!=p[pIdx]&&p[pIdx]!='?'){
            if (p[pIdx]=='*'){
                while (p[++pIdx]=='*') {}
                if (p[pIdx]==0){
                    return 1;
                }
                for (;s[sIdx]!=0;sIdx++){
                    if (s[sIdx]==p[pIdx]||p[pIdx]=='?'){ 
                        if (memo[sIdx+1][pIdx+1]==1) return memo[sIdx+1][pIdx+1];
                        if (memo[sIdx+1][pIdx+1]==-1){
                            if (memo[sIdx+1][pIdx+1] = check(s, p, sIdx+1, pIdx+1)) return 1;
                        }
                    } 
                }
                return 0;
            }
            else{ 
                return 0;
            }
        }
    }

    if (s[sIdx]==0&&p[pIdx]==0) {
        return 1;
    }
    else if (s[sIdx]==0) {
        while (p[pIdx]!=0) {
            if (p[pIdx++]!='*'){
                return 0;
            }
        }
        return 1;
    } 
    else{
        return 0;
    }
}

bool isMatch(char* s, char* p) {
    for(int i = 0; i < 2000; i++) {
        for(int j = 0; j < 2000; j++) memo[i][j] = -1;
    }

    return check(s,p,0,0);
}

即使在使用记忆优化之前，它也通过了大约 1,000 个测试用例， 但之后，它通过了大约 600 个测试用例。 我不知道会发生什么。

Answer 1

对于这个问题，您的代码过于复杂。在每一步中，您只需要尝试匹配一个字符，而不是迭代检查所有可能的匹配项。

让我们将其分解为具有

O(|s||p|)

时间复杂度的动态编程解决方案的情况（其中

|s|

表示字符串

s

的长度）。

小事例：

如果模式中没有剩余字符，则仅当要匹配的字符串本身为空时才能匹配。

如果字符串中没有更多字符，则仅当模式的其余部分仅包含星号时才能匹配。我们可以将其重写为模式的当前字符是星号，并且模式的其余部分也匹配。

其他案例：

如果字符串和模式的第一个字符匹配或者模式以

?

开头，那么我们只需将字符串的其余部分与模式的其余部分进行匹配。

如果模式的第一个字符是

*

，则它可以不匹配任何内容，也可以匹配字符串的第一个字符，并且有可能匹配更多字符。

否则，没有匹配。

int memo[2000][2000];

int check(char* s, char* p, int sIdx, int pIdx){
    if (!p[pIdx]) return !s[sIdx];
    if (!~memo[sIdx][pIdx]) {
        if (!s[sIdx]) memo[sIdx][pIdx] = p[pIdx] == '*' && check(s, p, sIdx, pIdx + 1);
        else if (s[sIdx] == p[pIdx] || p[pIdx] == '?')
            memo[sIdx][pIdx] = check(s, p, sIdx + 1, pIdx + 1);
        else if (p[pIdx] == '*')
            memo[sIdx][pIdx] = check(s, p, sIdx, pIdx + 1) || check(s, p, sIdx + 1, pIdx);
        else 
            memo[sIdx][pIdx] = 0;
    }
    return memo[sIdx][pIdx];
}

bool isMatch(char* s, char* p) {
    memset(memo, -1, sizeof memo);
    return check(s, p, 0, 0);
}