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

Question

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

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

匹配应该覆盖整个输入字符串（不是部分）。

函数原型应该是：
布尔isMatch（常量字符* S，常量字符* P）

一些例子：

• isMatch（ “AA”，” a“）→false
• isMatch（”aa“，”aa“）→true
• isMatch（”aaa“，”aa“）→false
• isMatch（ “AA”， “*”）→真
• isMatch（ “AA”， “A *”）→真
• isMatch（ “AB”， “*？”）→真
• isMatch（ “AAB”， “C * A * b”）→假

---

问题：

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

我个人认为，

• 时间复杂度高度家属对 “输入”，不能写 出像T = O（？）。
• 空间复杂度= O（min（sLen，pLen）），因为最大递归 depth = 0（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) 

现在一个，有经验，可以识别非常相似的一个复发binomial coefficients，使（当然稍微不可思议的）替代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，但它的混乱，如果我写的大西塔）。

到目前为止，我们已经证明只有T(s, p)是一个上限。由于*是比较麻烦的情况，所以最糟糕的情况出现了：使模式全部为* s。我们必须小心一点，因为如果比赛成功，那么可能会出现一些短路。但是，防止匹配所花的时间很少：请考虑字符串0000000000和**********1（根据需要调整0 s和*的数量）。这个例子表明，所引用的边界在多项式因子内是紧的（可以忽略，因为运行时间已经是指数）。

---

为了得到一个上限，没有必要精确地计算出这些重复。例如，我可能会猜测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)是一个有效的上限，虽然这个答案的其余部分的光它不紧。现在可以在界限中寻找浪费;例如，对于一个总体高估，我们可以得到指数基数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)