DP solution for c++


  • 0
    S

    dp[j][i] is the solution when we are at j in s and i in p,sum[j][i] is the sum of dp[j][k] where 0<=k<=i

    #include<bits/stdc++.h>
    #define FOR(i,a,b) for(int i = (a);i<=(b);i++)
    #define ROF(i,a,b) for(int i = (a);i>=(b);i--)
    #define FR(i,a,b) for(int i = (a);i<(b);i++)
    #define RF(i,a,b) for(int i = (a);i>(b);i--)
    #define MST(a,x) memset(a,x,sizeof(a))
    #define ll long long
    #define PB push_back
    #define PH push
    #define MP make_pair
    #define FT first
    #define SD second
    #define N 2005
    #define M 51
    #define INF 100000000000000007
    #define MOD 1000000007
    #define MOD2 1000000009
    #define eps 1e-14
    using namespace std;
    
    
    int dp[2][N],sum[2][N];
    class Solution {
    public:
        bool isMatch(string s, string p) {
            int ls,lp;
            ls = s.length();
            lp = p.length();
            if(ls == 0&&lp == 0)return 1;
            MST(dp[lp&1],0);
            MST(sum[lp&1],0);
            dp[lp&1][ls] = 1;
            sum[lp&1][ls] = 1;
            for(int j = lp-1;j>=0;j--)
            {
                int f = (j&1);
                MST(dp[f],0);
                MST(sum[f],0);
                for(int i = 0;i<=ls;i++)
                {
                    if(p[j] == '?')dp[f][i] |= dp[1-f][i+1];
                    else if(p[j] == '*')
                    {
                        if(i>0)dp[f][i] |= (sum[1-f][ls]-sum[1-f][i-1]>0);
                        else dp[f][i] |= (sum[1-f][ls]>0);
                    }
                    else if(i<ls&&s[i] == p[j])dp[f][i] |= dp[1-f][i+1];
    
                    if(i == 0)sum[f][i] = dp[f][i];
                    else sum[f][i] = sum[f][i-1]+dp[f][i];
                }
            }
            return dp[0][0];
        }
    };
    

Log in to reply
 

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