Accepted 4ms C++ dynamic programming with O(n) space


  • 0
    M
    class Solution {
    public:
        bool isMatch(string s, string p) {
            int n = (int)s.size(), m = (int)p.size();
            bool f[2*n+2], *f1=f, *f2=f+n+1;
            fill_n(f, 2*n+2, false);
            f1[n]=true;
            bool star = false;
            for (int j = m-1; j >= 0; j--) {
                if (p[j]=='*') {
                    star = true;
                    continue;
                } else {
                    if (!star) {
                        f2[n]=false;
                        for (int i = n-1; i >= 0; i--) {
                            if (s[i] == p[j] || (p[j] == '.'))
                                f2[i] = f1[i+1];
                            else
                                f2[i] = false;
                        }
                    } else {
                        f2[n]=f1[n];
                        for (int i = n-1; i >= 0; i--) {
                            int k = i;
                            f2[i] = false;
                            while (k < n && (s[k] == p[j] || p[j] == '.')) {
                                if (f1[k]) {
                                    f2[i] = true;
                                    break;
                                }
                                k++;
                            }
                            if (!f2[i])
                                f2[i]=f1[k];
                        }
                    }
                    star = false;
                }
                swap(f1, f2);
            }
            return f1[0];
        }
    };

  • 0
    X

    This is a big improvement over the O(n^2) space DP solution. Could you please help explain in details or point any reference? Thanks a lot!


  • 0
    M

    I would say just more practice. You understand O(n^2) DP version, then you will notice that you are working on the n^2 table row by row, and the current row only depends on the previous row. Now you know that this can be done with O(n) version. A bit tricky is that when the last row corresponds to '*', the current row depends on the row before the last row. Let me know if you need any further assistance.


  • 0
    X

    I see, you use extra loop to the row before the last row. Yes, I notice that each row i depends only itself, row i-1, and row i-2. In my implementation I just build 3 rows to store the information, instead of extra looping. The code is also linear space and 4ms. BTW, it seems to me that you do the matching backward, why is that? What's the gain?


  • 0
    M

    There are different approaches to the same problem, I just happen to adopt one of them. No magic here. I have another cleaner implementation as follows. Hope you will like that better.


  • 0
    M

    Another cleaner implementation with half space needed

    bool isMatch(string s, string p) {
        int ns = (int)s.size(), np = (int)p.size();
        bool f[ns+1];
        fill_n(f, ns+1, false);
        f[ns]=true;
        bool star=false;
        for (int j = np-1; j >= 0; j--) {
            if (p[j]=='*') {
                star=true;
                continue;
            } 
            if (!star) {
                for (int i = 0; i < ns; i++) {
                    if (p[j]=='.' || s[i]==p[j])
                        f[i]=f[i+1];
                    else
                        f[i]=false;
                } 
                f[ns]=false;
            } else {
                for (int i = 0; i < ns; i++) {
                    if (f[i]) continue;
                    for (int k = i; k < ns; k++) {
                        if (p[j]=='.' || s[k]==p[j]) {
                            if (f[k+1])
                                f[i]=true;
                        } else
                            break;
                    }
                }
             }
            star=false;
        }
        return f[0];
    }

Log in to reply
 

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