Shared my AC C++ clean code, can someone please tell me the complexity of my code?


  • -1
    R

    thanks, is this O(2^n)? I think it is very important to know the complexity of the solutions as in the interviews they mostly always ask for it.

    class Solution {
    public:
        bool isMatch(string s, string p) {
            return isMatch(s, s.size()-1, p, p.size()-1);
        }
    private:
        bool isMatch(string s, int i, string p, int j) {
            if(j==-1) return (i==-1);
            if(p[j]=='.'){
                return (i>=0 && isMatch(s, i-1, p, j-1));
            }else if(p[j]=='*'){
                if(isMatch(s, i, p, j-2)) return true; // match no element of string
                for(int k=i; k>=0; --k){
                    if(s[k]==p[j-1] || p[j-1]=='.') { 
                        if(isMatch(s, k-1, p, j-2)) return true; //try to match all possibilities
                    }else // if not match break
                        break;
                }
            }else{
                if(i>=0 && s[i]==p[j])  return isMatch(s, i-1, p, j-1);
            }
            return false;
        }
    };

Log in to reply
 

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