正则表达式匹配的时间复杂度

Question

我正在解决 leetcode 上的正则表达式匹配问题。我使用递归解决了它，如下所示：

    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));

但是在这里面我怎么才能找到代码的时间复杂度呢？

问题link：https://leetcode.com/problems/regular-expression-matching/

PS: 在解决方案中他们已经解释了时间复杂度，但我无法理解。

Answer 1

假设T(t,p)是函数isMatch(text, pattern)的时间复杂度，其中t是text.length()，p是pattern.length() / 2

所有 x

的第一个 T(x,0) = 1

那么如果pattern[1] == '*',T(t,p) = T(t,p-1) + T(t-1,p) + O(t + p)

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

显然第一种情况更糟

想想T的组合意义。最初是一个你在坐标 (t,p) 上的球，你可以一步将它移动到 (t-1,p) 或 (t,p-1)，花费 t+p。球停在轴上。然后 T(t,p) 等于将球移动到从 (t,p).

开始的轴的每种有效方式的总成本

那我们就知道了

所以总的时间复杂度是O((t+p)2^(t + p/2))

顺便说一句，如果您使用 std::string_view 而不是 .substr() 之类的东西，您的代码会运行更快，这会阻止复制整个字符串。

正则表达式匹配的时间复杂度

Time complexity for Regular Expression Matching

c++

algorithm

time-complexity