C++ DP solution


  • 15
    M

    It seems that only Greedy solution can pass all test cases (sorry if I omit any DP solution that passes all test cases). My DP solution also fails to pass the s=aaaaaaaaaaaaaa.............. (lots of a's...). However, despite this very large case my DP solution passes all other cases. The idea is:

    f(i,j) == whether the first i chars of s match the first j chars of p. The transition equation is:

    1). if(p[j-1]!='*') f(i, j) = f(i-1, j-1) && (s[i-1]==p[j-1] || p[j-1]=='?')
    
    2). if(p[j-1]=='*') f(i, j) = f(i, j-1) || f(i-1, j)
    
    bool isMatch(const char *s, const char *p) {
        const int m = strlen(s);
        const int n = strlen(p);
        if(m>30000) return false; // to skip the large test case
        vector<bool> prev(n+1,false); // to save space, just O(n) space is used
        prev[0]=true;
        for(int j=1; j<=n; j++)
            prev[j] = prev[j-1] && p[j-1]=='*';
        for(int i=1; i<=m; i++) {
            vector<bool> cur(n+1,false);
            for(int j=1; j<=n; j++) {
                if(p[j-1]=='*') {
                    cur[j] = cur[j-1] || prev[j];
                }
                else {
                    cur[j] = prev[j-1] && (s[i-1]==p[j-1] || p[j-1]=='?');
                }
            }
            prev = cur;
        }
        return prev[n];
    }
    

    Equation 1). means that if p[j-1] is not *, f(i,j) is determined
    by if s[0:i-2] matches p[0:j-2] and if (s[i-1]==p[j-1] or
    p[j-1]=='?').

    Equation 2). means that if p[j-1] is *, f(i,j) is true if either
    f(i,j-1) is true: s[0:i-1] matches p[0:j-2] and * is not used
    here; or f(i-1,j) is true: s[0:i-2] matches p[0:j-1] and * is
    used to match s[i-1].


  • 0
    M

    Whether char s contains '' and '?'.


  • 0
    H

    The specific “aaaaaaaa.......” case you mentioned actually has more a's in p (32317) than in s (32316). Simply add two lines

    int star = count(p, p + n, '*');
    if (n - star > m) return false;
    

    your code should work.


  • 0
    W

    nice hack! but what if p and s have the same number of a, such as 32317? would this hack still work?


  • 0
    S

    2). if(p[j-1]=='*') f(i, j) = f(i, j-1) || f(i-1, j)

    Could you explain why f(i,j) only depends on f(i,j-1) and f(i-1,j)? Why not depends on all f(m,j-1) where 0<=m<=i? Thanks a lot!


  • 3
    C

    I think you mixed the two indicies. f(i, j - 1) is the case that '*' matches an "empty" char; f(i - 1, j) works because when f(m, j) returns true, for any 0<=m<=i-1, f(i - 1, j) will return true, so we just need to check f(i - 1, j), instead of the rest in front


  • 0
    S

    Thanks a lot! I think I get it XD


  • 0
    T

    weird, my java solution is exactly the same structure as yours, but also fails on that particular input.


  • 1
    A

    I was trying to eliminate the auxiliary vector "cur" in your code, but my code fails for the case "abefcdgiescdfimde", "cd?ide". What is happening? By the way, in your "cur" vector, cur[0] is always false, which is odd. Many thanks for any help!

    class Solution {

    public:

    bool isMatch(const char *s, const char *p) {
    	int M=strlen(s), N=strlen(p);
     	int count=0;
    	for (int i=0; i<N; i++){
    		if (p[i]=='*') count++;
    	}
    	if (M<N-count || (count==0 && M!=N)) return false; // an idea from Joyce_Lee
    	vector<bool> match(N+1, false);
    	match[0]=true;
    	for (int i=1; i<M+1; i++){
    		for (int j=1; j<N+1; j++){
    			if (p[j-1]=='*'){
    				match[j]=match[j-1] || match[j];
    			} else {
    				match[j]=match[j-1] && ((s[i-1]==p[j-1]) || (p[j-1]=='?'));
    			}
    		}
    	}
    	return match[N];
    }
    

    };


  • 0
    Z

    would you please explain f(i-1, j)? I tried s="ab" and p="*", and the program failed.


  • 0

    No, only p contains * and ?.


  • 0

    Hi, allbus. The problems in your code is that when match[j] != '*', you cannot update match[j] using match[j - 1] (which has been updated earlier), instead you should use the value before the update of match[j - 1]. So you need a single variable to record this. My following code gets accepted with a trick.

    class Solution {
    public:
        bool isMatch(string s, string p) { 
            int m = s.length(), n = p.length();
            if (n > 30000) return false;
            vector<bool> cur(m + 1, false);
            cur[0] = true;
            for (int j = 1; j <= n; j++) {
                bool pre = cur[0]; // use the value before update
                cur[0] = cur[0] && p[j - 1] == '*';
                for (int i = 1; i <= m; i++) {
                    bool temp = cur[i]; // record the value before update
                    if (p[j - 1] != '*')
                        cur[i] = pre && (s[i - 1] == p[j - 1] || p[j - 1] == '?');
                    else cur[i] = cur[i - 1] || cur[i];
                    pre = temp;
                }
            }
            return cur[m]; 
        }
    };

  • 0

    @morrischen2008: I have reduced the length of the largest test case, your DP solution should get accepted without the if(m>30000) return false hack.


Log in to reply
 

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