DP solution. O(n) space O(n^2) time


  • 0
    A

    This is my accepted DP solution. O(n) space. O(n^2) time.
    As we need only the previous iteration's result, we can do this DP by using 2 1D arrays instead of a whole 2D matrix.

    bool isMatch(string s, string p)
    {
        int n = s.length(), m = p.length();
        int i = 0, j = 0;
        bool dp[2][10000] = {0};
        dp[0][0] = 1;
        
        while(i<m && p[i] == '*')
        {
            dp[0][i+1] = 1;
            i++;
        }
        int x = 0;
        for(i = 1; i <= n; i++)
        {
            x = x^1;
            for(j = 1; j <= m; j++)
            {
                if(p[j-1] == '*')
                    dp[x][j] = dp[x^1][j] || dp[x][j-1];
                else
                    dp[x][j] = dp[x^1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '?');
            }
            dp[x^1][0] = dp[x][0];
        }
        return dp[x][m];
    }

  • 1
    T

    My DP C++ Solution with time complexity O(nm) and space O(nm).Accepted! Time is 302 ms, although kind of embarrassing. The idea is simple. Note

    bool isMatch(const char* s, const char* p)
    {
    int slen = strlen(s), plen = strlen(p);

    bool **dp = new bool*[slen + 1];
    for(int i = 0; i <= slen; i++)
    	dp[i] = new bool[plen + 1];
    dp[0][0] = true;
    for(int i = 1; i <= plen; i++)
    	dp[0][i] = dp[0][i - 1]&&(p[i-1] == '*');
    for(int i = 1; i <= slen; i++)
    	dp[i][0] = false;
    for(int i = 1; i <= slen; i++)
    {
    	for(int j = 1; j <= plen; 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-1] || dp[i-1][j]; //Note here that if p[j-1] == '*', then p[j-1] can either match empty string or match s[i-1] in such case,p[i-1] should keep matching forward.
    	}
    }
    bool ret = dp[slen][plen];
    for(int i = 0; i <= slen; i++)
    	delete[] dp[i];
    delete[]dp;
    return ret;
    

    }


  • 0
    L

    same solution, but I use vector. It cost 1772 ms. ooooooooooooooooh.


  • 0
    Y

    Thanks! Your 2D-dp solution is very clear! Below is a JAVA version

    public boolean isMatch_2d_method(String s, String p) {
    	int m=s.length(), n=p.length();
    	boolean[][] dp = new boolean[m+1][n+1];
    	dp[0][0] = true;
    	for (int i=1; i<=m; i++) {
    		dp[i][0] = false;
    	}
    	
    	for(int j=1; j<=n; j++) {
    		if(p.charAt(j-1)=='*'){
    			dp[0][j] = true;
    		} else {
    			break;
    		}
    	}
    	
    	for(int i=1; i<=m; i++) {
    		for(int j=1; j<=n; j++) {
    			if (p.charAt(j-1)!='*') {
    				dp[i][j] = dp[i-1][j-1] && (s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='?');
    			} else {
    				dp[i][j] = dp[i-1][j] || dp[i][j-1];
    			}
    		}
    	}
    	return dp[m][n];
    }

Log in to reply
 

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