Evolve from brute force to optimal


  • 0

    This is similar to regular expression matching but more tricky.

    1. Recursion O(2^n), * matches 0 or more chars.
        bool isMatch(string s, string p) {
            return isMatch(0,0,s,p);    
        }
        bool isMatch(int i, int j, string& s, string& p) {
            int sn = s.size();
            if(j==p.size()) return i==sn;
            if(p[j]=='*') {
                for(int k=i;k<=sn;k++) if(isMatch(k,j+1,s,p)) return 1;
                return 0;
            }
            if(i<sn && (p[j]=='?'||s[i]==p[j])) return isMatch(i+1,j+1,s,p);
            return 0;
        }
    
    1. Use recursion instead of iteration when * matches non empty string, O(2^n)
        bool isMatch(string s, string p) {
            return isMatch(0,0,s,p);    
        }
        bool isMatch(int i, int j, string& s, string& p) {
            int sn = s.size();
            if(j==p.size()) return i==sn;
            if(p[j]=='*') return isMatch(i,j+1,s,p) || (i<sn && isMatch(i+1,j,s,p));
            if(i<sn && (p[j]=='?'|| s[i]==p[j])) return isMatch(i+1,j+1,s,p);
            return 0;
        }
    
    1. Memorization and dp based on #2 O(n^2), memorization turns out to be faster than dp. I think it is because dfs terminates as soon as a match is found but dp is always n^2.
        bool isMatch(string s, string p) {
            vector<vector<char>> mem(s.size()+1,vector<char>(p.size(),-1));
            return isMatch(0,0,s,p,mem);    
        }
        bool isMatch(int i, int j, string& s, string& p,vector<vector<char>> &mem) {
            int sn = s.size();
            if(j==p.size()) return i==sn;
            if(mem[i][j]!=-1) return mem[i][j];
            if(p[j]=='*') return mem[i][j]= isMatch(i,j+1,s,p,mem) || (i<sn && isMatch(i+1,j,s,p,mem));
            if(i<sn && (p[j]=='?'|| s[i]==p[j])) return mem[i][j]=isMatch(i+1,j+1,s,p,mem);
            return mem[i][j]=0;
        }
        bool isMatch(string s, string p) {
            int sn = s.size(), pn = p.size();
            vector<vector<bool>> dp(sn+1,vector<bool>(pn+1));
            dp[sn][pn]=1;
            for(int i=sn;i>=0;i--)
                for(int j=pn-1;j>=0;j--)
                    if(p[j]=='*') dp[i][j] = dp[i][j+1]||(i<sn && dp[i+1][j]);
                    else dp[i][j] = i<sn && (p[j]=='?'|| s[i]==p[j]) && dp[i+1][j+1]; 
            return dp[0][0];    
        }
    
    1. For most recursion to dp problems, we are done. However, we can still do better in this problem. A key observation is, we only need to backtrack from the current star. Say we use #1 and have 2 stars in p separated by characters. When we reach the 2nd star for the first time, there is a match right before it between s(0...i) and p(0...*...j). s(0...i) is the first/shortest substring that matches p(0...j) because we match * to chars incrementally. Matching the 2nd star starts from s[i+1]. If we backtrack the 1st star and match it with more characters then the next time when s(0...k) matche s p(0...j), k must be larger than i. At this point, matching the 2nd star starts from s[k+1]. Since k>i, so it is covered by just backtracking the 2nd star. Therefore backtracking the 1st star does not create more opportunities and we can ignore it. Code is based on #1.
        bool isMatch(string s, string p) {
            bool star = 0;
            return isMatch(star,0,0,s,p);    
        }
        bool isMatch(bool& star, int i, int j, string& s, string& p) {
            int sn = s.size();
            if(j==p.size()) return i==sn;
            if(p[j]=='*') {
                for(int k=i;k<=sn;k++) {
                    if(isMatch(star,k,j+1,s,p)) return 1;
                    if(star) return 0;
                }
                star = 1;
                return 0;
            }
            if(i<sn && (p[j]=='?'||s[i]==p[j])) return isMatch(star,i+1,j+1,s,p);
            return 0;
        }
    
    1. Iterative backtracking O(n^2), same as #4. Idea is from the top solution
        bool isMatch(string s, string p) {
            int i=0,j=0,star=-1,si=0;
            while(i<s.size()) {
                if(p[j]=='?'||s[i]==p[j]) {
                    i++;
                    j++;
                } else if (p[j]=='*') {
                    star = j++;
                    si = i;
                } else if (star >=0 ) {
                    i = ++si;
                    j = star+1;
                } else return 0;
            }
            while(j<p.size()) if(p[j++]!='*') return 0;
            return 1;
        }
    

Log in to reply
 

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