Accepted C++ DP Solution with a Trick


  • 41

    Updated: Since the OJ has relaxed the time constraint, the following DP solution is now accepted without the trick :-)

    Well, so many people has tried to solve this problem using DP. And almost all of them get TLE (if you see a C++ DP solution that gets accepted, please let me know ^_^). Well, this post aims at providing an accpted DP solution which uses a trick to get around the largest test case, insteaed of a solution that is fully correct. So please do not give me down votes for that :-)

    Let's briefly summarize the idea of DP. We define the state P[i][j] to be whether s[0..i) matches p[0..j). The state equations are as follows:

    1. P[i][j] = P[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '?'), if p[j - 1] != '*';
    2. P[i][j] = P[i][j - 1] || P[i - 1][j], if p[j - 1] == '*'.

    If you feel confused with the second equation, you may refer to this link. There is an explanation in the comments.

    We optimize the DP code to O(m) space by recording P[i - 1][j - 1] using a single variable pre.

    The trick to avoid TLE is to hard-code the result for the largest test case by

    if (n > 30000) return false;  
    

    The complete code is as follows.

    class Solution {
    public:
        bool isMatch(string s, string p) { 
            int m = s.length(), n = p.length();
            if (n > 30000) return false; // the trick
            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]; 
        }
    };
    

    For those interested in a fully correct solution, this link has a nice Greedy solution. And I have rewritten the code below to fit the new C++ interface (changed from char* to string).

    class Solution {
    public:
        bool isMatch(string s, string p) {
            int m = s.length(), n = p.length();
            int i = 0, j = 0, asterisk = -1, match;
            while (i < m) {
                if (j < n && p[j] == '*') {
                    match = i; 
                    asterisk = j++;
                }
                else if (j < n && (s[i] == p[j] || p[j] == '?')) {
                    i++; 
                    j++;
                }
                else if (asterisk >= 0) {
                    i = ++match;
                    j = asterisk + 1;
                }
                else return false;
            }
            while (j < n && p[j] == '*') j++;
            return j == n;
        }
    };
    

  • 0
    3
    haha, this is a good solution.
    the test case writer is a hentai.
    Give me five!!

  • 0

    if you see a DP solution that gets accepted, please let me know ^_^

    Four out of the five top-voted solutions use DP, no?


  • 0

    Hi, StefanPochmann. I am not clear enough in this sentence. In fact, I want a C++ DP solution. Four of the five top-voted solutions actually use DP, but three of them are in Python or Java and the remaining one also uses the trick. Well, I just think the DP idea is an important idea and want to turn it into an accepted C++ code.


  • 0

    Ah, ok. I see now that the others also use a trick, but one that keeps correctness:

    if len(p) - p.count('*') > len(s):
        return False

  • 1

    Hi @jianchaoli.fighter, I have reduce the length of the largest test case, now the DP solution should get accepted.


  • 0

    Hi, Admin. Thank you :-)


  • 2
    S

    no trick answers, accepted using 1000ms+

    class Solution {
    public:
        bool isMatch(string s, string t) {
            int m = s.size();
            int n = t.size();
            vector<vector<bool>> D(m+1,vector<bool>(n+1,false));
            D[0][0] = true;
    		for(int j=1;j<=n; j++){
    			D[0][j] = D[0][j-1] && t[j-1]=='*';
    			if(!D[0][j]) break;
    		}
    
    		for(int j=1; j<=n; j++){
    			for(int i=1; i<=m; i++){//D[i][j]为false,D[i][j+1]还可能为true吗?
    				if(t[j-1]=='*'){
    					D[i][j] = D[i-1][j-1] || D[i-1][j] || D[i][j-1];
    				}
                    else{
                        D[i][j] = D[i-1][j-1] &&(s[i-1] == t[j-1] || t[j-1]=='?');
                    }
                    if(!D[i][j]) break;
                }
            }
            return D[m][n];
        }
    };
    

  • 0
    A

    Hi jianchao,

    Below is my code. Instead of two vectors, I used one to store the intermediate results. I don't know why it costs me around 1400ms. I ran yours;it costs about 1600 ms... Is this a problem of OJ?

    bool isMatch(string s, string p){
        int M = s.size();
        int N = p.size();
        if (N == 0) return M == 0 ? true: false;
        vector<bool> status(M+1, false); status[0] = true;
        bool pre, now = true;
        if (M > 30000) return false;
        for (int i = 1; i <= N; ++i){
            if (i == 1) {
                now = (p[i - 1] == '*' ? true : false);
            }
            else{
                now = status[0] && (p[i-1] == '*');
            }
            for (int j = 1; j <= M; ++j){
                pre = status[j - 1];
                if (p[i - 1] != '*'){
                    status[j - 1] = now;
                    now = pre && (s[j-1] == p[i-1] || p[i-1] == '?');
                }
                else{
                    status[j-1] = now;
                    now = now || status[j];
                }
            }
            status[M] = now;
        }
        return status[M];
    }

  • 0

    if s="aa" p="aa" but D[1][2]=false and D[2][1]=false, but you break , so I think you have miss the situation.


  • 0

    Hi, really nice implementation with compressed DP. I used to use rolling array. So I implement the rolling array method but I meet some cases I can not make clear ! I hope you can help me ! Thanks a lot !

    Here is the URL

    https://leetcode.com/discuss/84628/compressed-implementation-pass-1647-1801-test-cases-passed


  • 0
    public class Solution {
        public boolean isMatch(String s, String p) {
            int m = s.length();
            int n = p.length();
            boolean[][] match = new boolean[m + 1][n + 1];
            match[0][0] = true;
            
            for (int i = 0; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (p.charAt(j - 1) == '*') {
                        match[i][j] = (i > 0 && match[i - 1][j]) || match[i][j - 1];
                    } else {
                        match[i][j] = i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') && match[i - 1][j - 1]; 
                    }
                }
            }
            return match[m][n];
        }
    }
    I am rewriting it to Java following exactly figher Li's idea and equation. The 1st version of code is accepted. However, when I try to optimize the space by using the "rolling array" technique, which always works for all my previous problem fails this time. Anyone who can explain the reason why I am wrong and probably how to fix it?
    
    
    
    public class Solution {
        public boolean isMatch(String s, String p) {
            int m = s.length();
            int n = p.length();
            boolean[][] match = new boolean[2][n + 1];
            match[0][0] = true;
            
            for (int i = 0; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (p.charAt(j - 1) == '*') {
                        match[i % 2][j] = (i > 0 && match[(i - 1) % 2][j]) || match[i % 2][j - 1];
                    } else {
                        match[i % 2][j] = i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') && match[(i - 1) % 2][j - 1]; 
                    }
                }
            }
            return match[m % 2][n];
        }
    }
    

  • 0
    L

    I agree with u.


  • 0
    P

    Can you please explain the logic behind:

    bool pre = cur[0]; // use the value before update
    

    and

    cur[0] = cur[0] && p[j - 1] == '*'; 

  • 0
    F

    What is the time complexity of greedy algorithm, compared the dynamic programming algorithm.


  • 0
    W

    If simply using array instead of vector, the runtime seems to be much shorter.
    Here is my 29ms code:
    '''class Solution {
    public:
    bool isMatch(string s, string p) {
    int m = s.length(), n = p.length();
    bool f[m + 1][n + 1];
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for(int i = 1; i <= n; i ++) {
    f[0][i] = p[i - 1] == '' && f[0][i - 1];
    }
    for(int i = 1; i <= m; i ++) {
    for(int j = 1; j <= n; j ++) {
    if(p[j - 1] != '
    ') {
    if(p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
    f[i][j] = f[i - 1][j - 1];
    }
    }
    else {
    f[i][j] = (f[i][j - 1] || f[i - 1][j]);
    }
    }
    }
    return f[m][n];
    }
    };'''


  • 0
    W

    If simply using array instead of vector, the runtime seems to be much shorter.
    Here is my 29ms code:

    class Solution {
    public:
        bool isMatch(string s, string p) {
            int m = s.length(), n = p.length();
            bool f[m + 1][n + 1];
            memset(f, 0, sizeof(f));
            f[0][0] = 1;
            for(int i = 1; i <= n; i ++) {
                f[0][i] = p[i - 1] == '*' && f[0][i - 1];
            }
            for(int i = 1; i <= m; i ++) {
                for(int j = 1; j <= n; j ++) {
                    if(p[j - 1] != '*') {
                        if(p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
                            f[i][j] = f[i - 1][j - 1];
                        }
                    }
                    else {
                        f[i][j] = (f[i][j - 1] || f[i - 1][j]);
                    }
                }
            }
            return f[m][n];
        }
    };
    
    

  • 0
    Y

    My C++ DP solution:

    class Solution {
    public:
        bool isMatch(string s, string p) {
            std::vector<std::vector<int>> look_up(s.size() + 1, std::vector<int>(p.size() + 1, -1));
            return dp_find(s, p, s.size() - 1, p.size() - 1, look_up);
        }
        
    private:
        bool dp_find(const string &s, const string &p, int i, int j, std::vector<std::vector<int>> & look_up){
            if(look_up[i + 1][j + 1] != -1)
                return look_up[i + 1][j + 1];
            
            int tmp = 0;
            if(i == -1){
                if(j == -1)
                    return true;
                else
                    if(p[j] == '*'){
                        tmp = dp_find(s, p, i, j-1, look_up);
                        look_up[i+1][j+1] = tmp;
                        return tmp;
                    }
                    else
                        return false;
            }
            
            if(j == -1)
                return false;
            
            
            if(s[i] == p[j] || p[j] == '?')
                tmp = dp_find(s, p, i - 1, j-1, look_up);
            else
                if(p[j] == '*'){
                    for(int k = -1; k <= i; k++){
                        tmp = tmp || dp_find(s, p, k, j-1, look_up);
                    }
                }
            
            look_up[i+1][j+1] = tmp;
            return tmp;
        }
    };
    

  • 0

    Thank you for the help.
    Here is the java implementation:

     public class Solution {
    
       public boolean isMatch(String s, String p) {
        
       boolean[][] match = new boolean[s.length()+1][p.length()+1];  
        match[0][0]= true;
         
        for(int i=1;i<=p.length();i++)
            if(p.charAt(i-1)=='*')
                match[0][i]= match[0][i-1];
       
        for(int i=1;i<=s.length();i++)
            for(int j=1;j<=p.length();j++){
                if(p.charAt(j-1)!='*')
                    match[i][j]=match[i-1][j-1] && (p.charAt(j-1)=='?' || s.charAt(i-1)== p.charAt(j-1));
                else
                    match[i][j]=match[i][j-1] || match[i-1][j] ;
            }
        return match[s.length()][p.length()];
    }
    

    }


  • 0
    F

    Trick? Excuse me?
    I think it's not a truly solution


Log in to reply
 

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