首页 > 代码库 > [LeetCode]Wildcard Matching 通配符匹配(贪心)
[LeetCode]Wildcard Matching 通配符匹配(贪心)
一开始采用递归写,TLE。
class Solution { public: bool flag; int n,m; void dfs(int id0,const char *s,int id1,const char *p){ if(flag)return; if(id0>=n){ if(id1>=m)flag=1; else{ int j=0; while(j<m&&p[j]=='*')j++; if(j>=m)flag=1; } return; } else if(id1>=m)return; if(p[id1]=='?'||p[id1]==s[id0]){ dfs(id0+1,s,id1+1,p); } else if(p[id1]=='*'){ for(int j=id0;j<n;++j) dfs(j,s,id1+1,p); } } bool isMatch(const char *s, const char *p) { for(n=0;s[n];++n); for(m=0;p[m];++m); flag=0; dfs(0,s,0,p); return flag; } };
粗剪枝了,还是超时。
看了下Discuss,发现可以贪心:
class Solution { public: bool isMatch(const char *s, const char *p) { const char*lastp=NULL,*lasts=NULL; while(*s){ if(*s==*p||*p=='?'){ p++; s++; } else if(*p=='*'){ //不匹配,只记录 lastp=p++; lasts=s; } else if(lastp!=NULL){ p=lastp+1; s=++lasts;//逐渐递增匹配1个字符、2个字符... } else return false; } while(*p&&*p=='*')p++; return *p=='\0'; } };
[LeetCode]Wildcard Matching 通配符匹配(贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。