What is time complexity of recursive solution?


  • 2
    I

    I think it is exponential, but I am not sure how to analyze it exactly, what is it?


  • 0
    B

    same question, is there any redundant calculation in recursion?


  • 0

    Let's first suppose that

    • the length of s is n
    • length of p is m

    The typical recursive solution will be as follows. One thing should be pointed out the searching tree of the recursion (each node will have one child or two at most):

    no matter what is to happen the index of either s or p will be incremented in the next recursive function so the worst case of the depth will be n+m

    but as we can clearly spot it that only when the *(p+1)=='*' there will be two sub-traversals and only when the isMatch(s, p+2) is false the second part will be checked - since they are connected by or; so the worst traversing case will be O(2^n).

    As for redundant checking, the simplest case is when there are several * which will definitely result in some small sub-searching-trees overlapping since each traversing branch will check all of its branch until the end.


    bool isMatch(char *s, char* p)
    {
        if(*p == '\0') return *s=='\0';
        if(*(p+1) == '*')
            return isMatch(s, p+2) ||  //match zero letter in s;
                ((*s==*p || '.'==*p) && isMatch(++s, p)); //match one or more;
        else
            return *s!='\0' && (*s==*p || '.'==*p) && isMatch(++s, ++p);
    }

  • 0

    It is roughly O(m+n choose n).
    check my post for some analysis


Log in to reply
 

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