首页 > 代码库 > 第八周 Leetcode 44. Wildcard Matching 水题 (HARD)
第八周 Leetcode 44. Wildcard Matching 水题 (HARD)
Leetcode 44
实现一种类似正则表达式的字符串匹配功能。
复杂度要求不高, 调代码稍微费点劲。。
好像跟贪心也不太沾边, 总之 *把待匹配串分成若干个子串, 每一个子串尽量在模式串中靠前的部分匹配完成就算贪心了吧。。
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; } } };
第八周 Leetcode 44. Wildcard Matching 水题 (HARD)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。