# What is time complexity of recursive solution?

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

• same question, is there any redundant calculation in recursion?

• 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);
}``````

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

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