实现一种类似正则表达式的字符串匹配功能。
复杂度要求不高， 调代码稍微费点劲。。
好像跟贪心也不太沾边， 总之 *把待匹配串分成若干个子串， 每一个子串尽量在模式串中靠前的部分匹配完成就算贪心了吧。。
class Solution {
public:
bool match(string &s,string &p,int l2,int r2,int l1)
{
if(l2==r2)return true;
if(l1+r2-l2-1>=s.length())return false;
while(l2<r2)
{
if(p[l2]=='?'){l1++;l2++;continue;}
if(s[l1]!=p[l2])return false;
l1++;l2++;
}
return true;
}
bool isMatch(string s, string p) {
s.append(1,'#');p.append(1,'#');
int l1=0,l2=0,r1=0,r2=0,len1=s.length(),len2=p.length();
while(true)
{
while(r2<len2&&p[r2]!='*')
r2++;
while(!match(s,p,l2,r2,l1))
{
if(l1>=len1)return false;
if(l2>0&&p[l2-1]=='*')l1++;
else return false;
}
l1+=r2-l2;
l2=r2+1;
r2=l2;
if(l1>=len1&&r2>=len2)return true;
if(r2>=len2)return false;
}
}
};