这种通配符匹配算法的时间复杂度是多少？

Question

通配符匹配
实现通配符模式匹配，并支持' ？'和' * '。

• '？' 匹配任何单个字符。
• '*'匹配任何字符序列（包括空序列）。

匹配项应覆盖整个输入字符串（而非部分）。

函数原型应为：
bool isMatch（const char * s，const char * p）

一些例子：

• isMatch（“ aa”，“ a”）吗？假
• isMatch（“ aa”，“ aa”）吗？真正
• isMatch（“ aaa”，“ aa”）吗？假
• isMatch（“ aa”，“ *”）吗？真正
• isMatch（“ aa”，“ a *”）吗？真正
• isMatch（“ ab”，“？*”）吗？真正
• isMatch（“ aab”，“ c * a * b”）吗？假

---

题：

• 什么时间复杂？
• 什么是空间复杂度？

我个人认为

• 时间复杂度高度依赖于“输入”，不能像T = O（？）那样写出来。
• 空间复杂度= O（min（sLen，pLen）），因为最大递归深度= O（min（sLen，pLen））。

尝试过：
写出时间复杂度表达式，然后画出递归树：

TC Expression => T(n) = T(n - 1) + O(1),            when pChar == '?' or pChar == sChar,
                      = T(n - 1) + T(n - 1) + O(1), when pChar == '*'.

我试图绘制递归树，但无法根据这种时间复杂度表达式弄清楚如何绘制它。

附加问题：
准确地说，我希望知道如何计算这种递归的时间复杂度，这种递归基于输入具有多个无法预料的分支。

注意：

• 我知道迭代解决方案和递归解决方案，但是无法弄清楚如何计算递归解决方案的时间复杂度。
• 而且这不是家庭作业，这个问题来自“ leetcode.com”，我只是希望知道该方法如何为这种特殊的递归计算时间复杂度。

---

代码： Java，解决方案：递归。

public class Solution {
    public boolean isMatch(String s, String p) {
        // Input checking.
        if (s == null || p == null) return false;

        int sLen = s.length();
        int pLen = p.length();

        return helper(s, 0, sLen, p, 0, pLen);
    }

    private boolean helper(String s, int sIndex, int sLen,
                           String p, int pIndex, int pLen) {
        // Base case.
        if (sIndex >= sLen && pIndex >= pLen) return true;
        else if (sIndex >= sLen) {
            // Check whether the remaining part of p all "*".
            while (pIndex < pLen) {
                if (p.charAt(pIndex) != '*') return false;
                pIndex ++;
            }
            return true;

        } else if (pIndex >= pLen) {
            return false;
        }

        char sc = s.charAt(sIndex);
        char pc = p.charAt(pIndex);

        if (pc == '?' || pc == sc) {
            return helper(s, sIndex + 1, sLen, p, pIndex + 1, pLen);

        } else if (pc == '*') {
            return helper(s, sIndex, sLen, p, pIndex + 1, pLen) ||
                   helper(s, sIndex + 1, sLen, p, pIndex, pLen);

        } else return false;
    }
}

Answer 1

为了在最坏的情况下运行时间达到上限（即big-O），您需要假设最坏的情况。匹配长度字符串和长度s模式的渐近运行时间的上限的正确递归p如下。

T(s, p) | s == 0 || p == 0 = 1
        | s >  0 && p >  0 = 1 + max(T(s, p - 1) + T(s - 1, p),  // *
                                     T(s - 1, p - 1))            // ? or literal

解决这样的两变量递归可能很棘手。在这种特殊情况下，可以通过归纳法很容易地显示出T这两个参数都不会减少，因此我们可以简化最大值。

T(s, p) | s == 0 || p == 0 = 1
        | s >  0 && p >  0 = 1 + T(s, p - 1) + T(s - 1, p)

现在，有经验的人可以认识到与二项式系数的递归非常相似，并进行了（当然有些不可思议的）替换s = n - k和p = k和T(s, p) = 2 U(n, k) - 1。

2 U(n, k) - 1 | n == k || k == 0 = 1
              | n >  k && k >  0 = 1 + 2 U(n - 1, k - 1) - 1 + 2 U(n - 1, k) - 1

U(n, k) | n == k || k == 0 = 1
        | n >  k && k >  0 = U(n - 1, k - 1) + U(n - 1, k)

我们得出的结论是，T(s, p) = 2 U(s + p, p) - 1 = 2 ((s + p) choose p) - 1 = O(2^(s + p)/sqrt(s + p))以斯特林的近似值（这是单个数量中可能的最佳大O界限s + p，但是如果我写大Theta的话，会令人困惑）。

到目前为止，我们仅证明这T(s, p)是一个上限。由于*是最麻烦的情况，因此出现了最坏情况的想法：将模式全为*s。我们必须小心一点，因为如果匹配成功，则可能会发生短路。但是，它几乎不需要阻止匹配：考虑字符串0000000000和模式**********1（根据需要调整0s 的数量*）。此示例显示引用的边界严格在多项式因子之内（可以忽略，因为运行时间已经是指数的了）。

为了获得一个上限，没有必要如此精确地计算出这些重复。例如，我可能会猜测T(s, p) <= 3^(s + p)并继续通过归纳来验证该主张。

T(s, p) | s = 0 || p = 0  = 1 <= 3^(s + p)                 // base case
        | s > 0 || p > 0  = 1 + T(s, p - 1) + T(s - 1, p)  // induction
                         <= 3^(s + p - 1) + 3^(s + p - 1) + 3^(s + p - 1)
                          = 3^(s + p)

现在，3^(s + p)是一个有效的上限，尽管鉴于此答案的其余部分，它并不严格。现在人们可以在边界寻找废物；1 <= 3^(s + p - 1)，例如，是一个总的高估，通过一些技巧，我们可以获得指数基数2。

但是，更重要的业务顺序是获得指数下限。通过为上面的不良示例绘制递归树，我可以推测出T(s, p) >= 2^min(s, p)。可以通过归纳来验证。

T(s, p) | s = 0 || p = 0  = 1 >= 2^min(s, p) = 2^0 = 1             // base case
        | s > 0 && p > 0  = 1 +     T(s, p - 1) +     T(s - 1, p)  // induction
                         >=     2^min(s, p - 1) + 2^min(s - 1, p)
                         >= 2^(min(s, p) - 1) + 2^(min(s, p) - 1)
                          = 2^min(s, p)