'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
贪心算法就是遇到*开始记录位置并不断尝试匹配,开始*匹配0字符失败后*匹配1字符再试,匹配到下一个*就终止了又开始记录位置后尝试匹配...
bool isMatch(string s, string p) {
return isMatchB(s.c_str(),p.c_str());
}
bool isMatchB(const char *s, const char *p) {
const char* star=nullptr;
const char* ss=nullptr;
while (*s){
if ((*p=='?')||(*p==*s)){++s;++p;continue;}
if (*p=='*'){star=++p; ss=s;continue;}
if (star){ p = star; s=++ss;}
else return false;
}
while (*p=='*'){++p;}
return !*p;
}
递归版本却是碰到*后从0开始递增s然后调用自己直到成功或s到了尾部:
while(*p=='*')++p;
do
{
if(isMatchC(s, p))
{ return true;
}
} while(*++s);
return isMatchC(s, p);
算法很易懂;但没找到证明感觉如芒在背.想了很久没发现怎么证明贪心法是"最优"的办法.
但后来想想证明最优干嘛?其实只要证明比递归版本效率并和它一样正确就行了....
证明如下:
base
1.模式p里没有*，平凡的匹配，递归版本和贪心版本一样效率.
2.模式p里一个*,递归版递归后的匹配和贪心版本(毕竟贪心版本不会碰到*了)算法一样.
3.模式p有两个*
p: same*abc*xxxxxx. (x代表任意字符和?)
s: same....abcxxxxxxx (.代表任意不含abc的字符x代表任意字符)
贪心版本匹配到第二个*后s剩下abc后面部分,第二个*可以任意扩展使得后段的x匹配为止
递归版本碰到第一个*后递归求abc*xxxxxxx与....abcxxxxxxx匹配
看起来和贪心版本一样效率，不效率的地方就在于:
匹配失败后贪心版本就失败了而递归版本屁颠颠的又挪动s到下一个试图匹配,递归版本不会成功的，因为第二个*失败就说明了后段的xxxxx之间子串不匹配
现在假设模式p有k个*且贪心版本更效率且一样正确.
4.p有k+1个*.
p: xxxx*abc*...... (.代表任意字符和*)
s: xxxx....abcdef..... (.代表任意不含abc的字符)
在第二个*之前使用贪心算法，匹配完毕碰到第二个*转调用递归版本的话,开头匹配情况落入base 1和base 2.递归版本则处理:
p: *.....
s: def.....
即落入假设模式里k个*里换用贪心版本更优秀且正确的情况里了
这样的话就归纳证明了贪心版本在正确匹配时不比递归版本差;在失败时比递归版本效率.