CODEWITHSUNDEEP
c++algorithmtime-complexity
hjhku
hjhku

Reputation: 181

Time complexity for Regular Expression Matching

I was solving the problem Regular Expression Matching on leetcode. I solved it using recursion as below:

    if (p.empty())    return s.empty();
    
    if ('*' == p[1])
        // x* matches empty string or at least one character: x* -> xx*
        // *s is to ensure s is non-empty
        return (isMatch(s, p.substr(2)) || !s.empty() && (s[0] == p[0] || '.' == p[0]) && isMatch(s.substr(1), p));
    else
        return !s.empty() && (s[0] == p[0] || '.' == p[0]) && isMatch(s.substr(1), p.substr(1));

But in this how can I find the time complexity of the code?

Problem link: https://leetcode.com/problems/regular-expression-matching/

PS: In solution they have explained the time complexity but I could not understand that.

Upvotes: 0

Views: 345

Answers (1)

Jacder Zhang
Jacder Zhang

Reputation: 126

Assume T(t,p) is the time complexity of function isMatch(text, pattern) where t is text.length() and p is pattern.length() / 2

First T(x,0) = 1 for all x

Then if pattern[1] == '*', T(t,p) = T(t,p-1) + T(t-1,p) + O(t + p)

Otherwise T(t,p) = T(t-1, p-0.5) + O(t + p)

Obviously the first case is worse

Think about the Combination Meaning of T. Originally the is a ball you on coordinate (t,p), in one step you can move it to (t-1,p) or (t,p-1), costing t+p. The ball stop on axis. Then T(t,p) equals to the total cost of each valid way to move the ball to axis starting from (t,p).

Then we know

enter image description here

So the total time complexity is O((t+p)2^(t + p/2))

BTW your code will run faster if you use something like std::string_view instead of .substr(), which prevents copying the whole string.

Upvotes: 2

Related Questions