'?' 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
貪心算法就是遇到*開(kāi)始記錄位置并不斷嘗試匹配,開(kāi)始*匹配0字符失敗后*匹配1字符再試,匹配到下一個(gè)*就終止了又開(kāi)始記錄位置后嘗試匹配...
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開(kāi)始遞增s然后調(diào)用自己直到成功或s到了尾部:
while(*p=='*')++p;
do
{
if(isMatchC(s, p))
{ return true;
}
} while(*++s);
return isMatchC(s, p);
算法很易懂;但沒(méi)找到證明感覺(jué)如芒在背.想了很久沒(méi)發(fā)現(xiàn)怎么證明貪心法是"最優(yōu)"的辦法.
但后來(lái)想想證明最優(yōu)干嘛?其實(shí)只要證明比遞歸版本效率并和它一樣正確就行了....
證明如下:
base
1.模式p里沒(méi)有*，平凡的匹配，遞歸版本和貪心版本一樣效率.
2.模式p里一個(gè)*,遞歸版遞歸后的匹配和貪心版本(畢竟貪心版本不會(huì)碰到*了)算法一樣.
3.模式p有兩個(gè)*
p: same*abc*xxxxxx. (x代表任意字符和?)
s: same....abcxxxxxxx (.代表任意不含abc的字符x代表任意字符)
貪心版本匹配到第二個(gè)*后s剩下abc后面部分,第二個(gè)*可以任意擴(kuò)展使得后段的x匹配為止
遞歸版本碰到第一個(gè)*后遞歸求abc*xxxxxxx與....abcxxxxxxx匹配
看起來(lái)和貪心版本一樣效率，不效率的地方就在于:
匹配失敗后貪心版本就失敗了而遞歸版本屁顛顛的又挪動(dòng)s到下一個(gè)試圖匹配,遞歸版本不會(huì)成功的，因?yàn)榈诙€(gè)*失敗就說(shuō)明了后段的xxxxx之間子串不匹配
現(xiàn)在假設(shè)模式p有k個(gè)*且貪心版本更效率且一樣正確.
4.p有k+1個(gè)*.
p: xxxx*abc*...... (.代表任意字符和*)
s: xxxx....abcdef..... (.代表任意不含abc的字符)
在第二個(gè)*之前使用貪心算法，匹配完畢碰到第二個(gè)*轉(zhuǎn)調(diào)用遞歸版本的話,開(kāi)頭匹配情況落入base 1和base 2.遞歸版本則處理:
p: *.....
s: def.....
即落入假設(shè)模式里k個(gè)*里換用貪心版本更優(yōu)秀且正確的情況里了
這樣的話就歸納證明了貪心版本在正確匹配時(shí)不比遞歸版本差;在失敗時(shí)比遞歸版本效率.