C++ recursive solution and DP solution


  • 13
    I

    recursive solution:

    bool isMatch(const char *s, const char *p) {
        if(!*p) return !*s;
        if(!*s) return *(p+1)=='*' && isMatch(s, p+2);
        if(*(p+1)=='*')
            return isMatch(s, p+2) || (*s==*p || *p=='.') && isMatch(s+1, p);
        else
            return (*s==*p || *p=='.') && isMatch(s+1, p+1);
    }
    

    DP solution:

    bool isMatch(const char *s, const char *p) {
        const int m=strlen(s), n=strlen(p);
        bool arr[m+1][n+1];
        fill_n(*arr, (m+1)*(n+1), false);
        arr[0][0]=true;
        for(int j=2; j<=n; j+=2)
            if(arr[0][j-2] && p[j-1]=='*')
                arr[0][j]=true;
            else
                break;
        for(int i=1; i<=m; ++i)
            for(int j=1; j<=n; ++j)
                if(p[j-1]=='*')
                    arr[i][j]=arr[i][j-2] || arr[i-1][j] && (s[i-1]==p[j-2] || p[j-2]=='.');
                else
                    arr[i][j]=arr[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='.');
        return arr[m][n];
    }

  • 8
    Y

    to your recursive answer, this input will definetely lead to a TLE:

    aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
    a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.