通配符匹配算法的时间复杂度是多少？
通配符匹配
实现通配符模式匹配，支持' ？ '和' * '。
匹配应覆盖整个输入字符串（不是部分）。
函数原型应该是：
bool isMatch（const char * s，const char * p）
一些例子：
题：
我个人认为
试过：
写出时间复杂度表达式，然后绘制递归树：
TC Expression => T(n) = T(n - 1) + O(1), when pChar == '?' or pChar == sChar,
= T(n - 1) + T(n - 1) + O(1), when pChar == '*'.
我试图绘制递归树，但无法弄清楚如何基于这种时间复杂表达式来绘制它。
附加问题：
准确地说，我希望知道如何计算这种递归的时间复杂度，这种递归具有基于输入的多不可预见分支。
注意：
代码： 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;
}
}
为了在最坏的情况下获得上限（即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))通过斯特林的逼近（这是单数量s + p可能的最好的大O界限，但如果我写big-Theta则会令人困惑）。
到目前为止，我们只证明T(s, p)是一个上界。 由于*是比较麻烦的情况下，最坏情况下的想法提出了自己：做模式的所有*秒。 我们必须小心一点，因为如果比赛成功，那么可能会出现一些短路。 但是，防止匹配所需的时间很少：请考虑字符串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)是一个有效的上限，但考虑到这个答案的其余部分并不严格。 现在可以在界限中寻找浪费; 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)
上一篇: What's time complexity of this algorithm for Wildcard Matching?