My answer using dynamic programming(4ms)


  • 0
    B
    class Solution {
    public:
    bool isMatch(string s, string p) {
    	int m = s.length();
    	int n = p.length();
    
    	bool **dp = new bool*[m+1];
    	for(int i = 0; i <= m; i ++){
    		dp[i] = new bool[n+1];
    		for(int j = 0; j <= n; j ++){
    			dp[i][j] = false;
    		}
    	}
    
    	dp[0][0] = true;
    	for (int i = 1; i <= n; i ++){
    		if(p[i-1] != '*') dp[0][i] = false;
    		else dp[0][i] = dp[0][i-2];
    	}
    
    	for(int i = 1; i <= m; i ++){
    		for(int j = 1; j <= n; j ++){
    			if(p[j-1] != '*'){
    				dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');
    			}else{
    				dp[i][j] = dp[i][j-2] || dp[i][j-1] || (dp[i-1][j-1] && (s[i-1] == p[j-2] || p[j-2] == '.'))
    					|| (dp[i - 1][j] && (s[i-1] == p[j-2] || p[j-2] == '.')); 
    			}
    		}
    	}
    
    	return dp[m][n];
    }
    

    };


Log in to reply
 

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