题解 | #通配符匹配# 一维数组DP

public:
    bool isMatch(const char *s, const char *p) {
        int ls = strlen(s),lp = strlen(p);
        if(ls != 0 && lp == 0)  return false;//s非空，p为空
        int dp[lp+1];
        memset(dp,0,sizeof(dp));
        dp[0] = 1;//s和p均为空
        for(int i=0;i<lp;i++){
            if(p[i]!='*')break;
            else{
                dp[i+1] = 1;//p的所有前缀*匹配s为空
            }
        }
        for(int i=1;i<=ls;i++){
            int pre = 0;//记录dp[i-1][0]
            for(int j=1;j<=lp;j++){
                if(i==1 && j==1)pre = 1;//dp[0][0]为1其他为0
                int tem = dp[j];
                if(s[i-1] == p[j-1] || p[j-1] == '?'){
                    dp[j] = pre;
                }else if(p[j-1] == '*'){
                    dp[j] = pre | dp[j] | dp[j-1];
                }else{
                    dp[j] = 0;//s[i-1] != p[j-1]且p[j-1]不为'?'和'*'则不匹配
                }
                pre = tem;
            }
        }
        return dp[lp];
    }
};