8ms backtracking solution C++


  • 5
    X
    //regular expression matching
    //first solution: using recursive version
    class Solution {
    public:
        bool isMatch(string s, string p) {
            int m = s.length(), n = p.length();
            return backtracking(s, m, p, n);
        }
        
        bool backtracking(string& s, int i, string& p, int j) {
            if (i == 0 && j == 0) return true;
            if (i != 0 && j == 0) return false;
            if (i == 0 && j != 0) {
                //in this case only p == "c*c*c*" this pattern can match null string
                if (p[j-1] == '*') {
                    return backtracking(s, i, p, j-2);
                }
                return false;
            }
            //now both i and j are not null
            if (s[i-1] == p[j-1] || p[j-1] == '.') {
                return backtracking(s, i - 1, p, j - 1);
            } else if (p[j-1] == '*') {
                //two cases: determines on whether p[j-2] == s[i-1]
                //first p[j-2]* matches zero characters of p
                if (backtracking(s, i, p, j - 2)) return true;
                //second consider whether p[j-2] == s[i-1], if true, then s[i-1] is matched, move to backtracking(i - 1, j)
                if (p[j-2] == s[i-1] || p[j-2] == '.') {
                    return backtracking(s, i - 1, p, j);
                }
                return false;
            }
            return false;
        }
    };

  • 0
    Z

    my DFS solution which takes 700ms, I hava no idea why it runs so slowly?

    bool isMatch(string s, string p) {
        bool res = false;
        backTrack(s,p, 0, 0, res);
        
        return res;
    }
    void backTrack(string s, string p, int posOfS, int posOfP, bool& res){
        ///< 类似于剪枝函数,既然有一个路径走通了,知道可以匹配了,所以其他的就可以直接返回了
        if(res == true) return;///< 一旦有一个路径可以找到,大家都回家
        ///< 如果s与p可以同时走完全程,那么我们就认为找到路径了
        if(posOfS==s.size() && posOfP==p.size()){
            res=true;  ///< 如果能够两个字符串都可以走完,走到桥的另一头,也就是找到路le
            return;
        }else if(posOfP==p.size()){
            return;    ///< 如果p率先走完全程,另一个不陪他玩了。。。
        }else if(posOfS==s.size()){
            while(posOfP<p.size()-1 && (p[posOfP]!='*' && p[posOfP+1]=='*')){
                posOfP+=2;
            }
            if(posOfP==p.size()){
                res=true;
            }
            return;
        }
       
        if(posOfP<p.size()-1 && p[posOfP+1]=='*'){
            backTrack(s,p,posOfS,posOfP+2,res);
            if(s[posOfS]==p[posOfP] || p[posOfP]=='.'){
                backTrack(s,p,posOfS+1,posOfP,res);
            }
        }else{
            if(p[posOfP]==s[posOfS] || p[posOfP]=='.'){
                backTrack(s,p,posOfS+1,posOfP+1,res);
            }
        }
    }

  • 0
    Z

    your explanation is truly clear and brief . 3Q very much!
    And, by using DFS, we exactly avoid reviewing a character repeatedly, in which way we will have the same time complexity with dynamic programming!


  • 1
    X

    (1) If you change the backTrack defination to this:
    void backTrack(string& s, string& p, int posOfS, int posOfP, bool& res)

    The runtime will be 156ms.

    (2) I believe that this line:
    if(res == true) return;///< 一旦有一个路径可以找到,大家都回家
    cannot ensure once a pattern match is found, the dfs solution process (which is a tree structure process) exit globally, maybe you still need to set the res value as the return value of backTrack() function, in this way, in these lines:

    if(posOfP<p.size()-1 && p[posOfP+1]=='*'){
        backTrack(s,p,posOfS,posOfP+2,res);
        if(s[posOfS]==p[posOfP] || p[posOfP]=='.'){
            backTrack(s,p,posOfS+1,posOfP,res);
        }
    

    You can judge whether the return value is true, if it's true, exit. (In this way, you can exit from the dfs solution tree globally).

    I have optimized your code to 136ms (however, I cannot optimize it any more):

    class Solution {
    public:
        bool isMatch(string s, string p) {
            //bool res = false;
            return backTrack(s,p, 0, 0);
    
            // return res;
        }
        bool backTrack(string& s, string& p, int posOfS, int posOfP){
            ///< 类似于剪枝函数,既然有一个路径走通了,知道可以匹配了,所以其他的就可以直接返回了
            ///< 如果s与p可以同时走完全程,那么我们就认为找到路径了
            if(posOfS==s.size() && posOfP==p.size()){
                return true;  ///< 如果能够两个字符串都可以走完,走到桥的另一头,也就是找到路le
            }else if(posOfP==p.size()){
                return false;    ///< 如果p率先走完全程,另一个不陪他玩了。。。
            }else if(posOfS==s.size()){
                while(posOfP<p.size()-1 && (p[posOfP]!='*' && p[posOfP+1]=='*')){
                    posOfP+=2;
                }
                if(posOfP==p.size()){
                    return true; //res=true;
                }
                return false;
            }
    
            if(posOfP<p.size()-1 && p[posOfP+1]=='*'){
                if ( backTrack(s,p,posOfS,posOfP+2) ) return true; //add judge condition
                if(s[posOfS]==p[posOfP] || p[posOfP]=='.'){
                    return backTrack(s,p,posOfS+1,posOfP);
                }
                return false;
            }else{
                if(p[posOfP]==s[posOfS] || p[posOfP]=='.'){
                    return backTrack(s,p,posOfS+1,posOfP+1);
                }
                return false;
            }
        }
    };
    

  • 0
    X

    No problem! Thanks you!


  • 0

    I have a questions, there are a few places have the potential of overflow, and there is not condition check such as for (j - 2 >= 0) for p[j - 2], however, it seems that it can be compiled without problem. What is the reason behind it?
    e.g. if s = "", p="*"


  • 0
    X

    @Ximin.Z It's because we assume the test case is right, we do not consider the case like:

    s = "aaaaa", p = "*"

    because it's invalid.


Log in to reply
 

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