Simple to understand recursive and DP solutions in C++


  • 0
    Y

    DP Solution :

    bool isMatchDP(string s, string p)
    {
    	bool dp[s.length()+1][p.length()+1];
    	memset(dp,0,sizeof(dp));
    
    	dp[0][0]=1;
    	for (int i = 1; i <= s.length(); ++i)
    		dp[i][0]=0;
    	for (int j = 1; j <= p.length(); ++j)
    	{
    		if(p[j-1]=='*')
    			dp[0][j] = dp[0][j-2];
    		else
    			dp[0][j]=  0;
    	}
    
    	for (int i = 1; i <= s.length(); ++i)
    	{
    		for (int j = 1; j <= p.length(); ++j)
    		{
    			dp[i][j]=0;
    			if(s[i-1] == p[j-1] || p[j-1]=='.')
    				dp[i][j] =  dp[i-1][j-1];
    			else if( p[j-1]=='*')
    			{
    				if(dp[i][j-2] == 1)
    					dp[i][j]=1;
    				else if (s[i-1] == p[j-2] || p[j-2]=='.')
    					dp[i][j] = dp[i-1][j];
    			}
    		}
    	}
    	return dp[s.length()][p.length()];
    }
    

    Recursive Solution :

    bool isMatch(char* s, char* p)
    {
    	if(p[0]=='\0'){
    		if(s[0]=='\0')
    			return true;
    		return false;	
    	}
    
    	if(s[0]=='\0'){
    		if(p[1]=='*')
    			return isMatch(s,p+2);
    		return false;
    	}
    
    	if(p[1]=='*')
    	{
    		if( isMatch(s,p+2) )
    			return true;
    		if(s[0]==p[0] || p[0]=='.')
    			return isMatch(s+1,p);
    	}
    
    	if(s[0]==p[0] || p[0]=='.')
    		return isMatch(s+1,p+1);
    
    	return false; 
    }
    

Log in to reply
 

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