通配符匹配算法的時間複雜度是多少？

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)