[LeetCode]Wildcard Matching 通配符匹配(贪心)
LeetCode 匹配 贪心 通配符 matching
2023-09-14 09:06:21 时间
一開始採用递归写。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'; } };
採用DP:
用dp[i,j]表示s[0,..,i]与p[0,..,j]是否匹配
dp[i,j]=1 if (p[j]=='*'&&(dp[i-1,j]||dp[i][j-1]||dp[i-1][j-1]))
dp[i,j]=1 if ((p[j]=='?'||s[i]==p[j]])&&dp[i-1][j-1])
时间复杂度O(nm),能够採用滚动数组,否则会超内存。空间复杂度O(m)
可是,会超时
bool isMatch(const char *s, const char *p) { int n=strlen(s),m=strlen(p),i,j; bool **dp=new bool*[2]; for(i=0;i<2;++i){ dp[i]=new bool[m+1]; memset(dp[i],0,sizeof(bool)*(m+1)); } dp[0][0]=1; bool flag=0; for(i=1;i<=n;++i){ for(j=1;j<=m;++j){ if(dp[flag][j-1]&&(p[j-1]=='?'||s[i-1]==p[j-1])) dp[1-flag][j]=1; else if(p[j-1]=='*'&&(dp[flag][j-1]||dp[flag][j]||dp[1-flag][j-1])) dp[1-flag][j]=1; } flag=1-flag; } bool ans=dp[1][m]; for(i=0;i<2;++i)delete[] dp[i]; delete[]dp; return ans; }
相关文章
- ☆打卡算法☆LeetCode 225. 用队列实现栈 算法解析
- LeetCode笔记:Weekly Contest 302
- 拒绝无脑刷LeetCode,你需要知道这些套路
- LeetCode刷题系列(4)
- LeetCode周赛297,一小时AK你也可以
- LeetCode周赛291,最后5分钟连A两题,不放弃才皆有可能
- ☆打卡算法☆LeetCode 199. 二叉树的右视图 算法解析
- LeetCode 1389. 按既定顺序创建目标数组
- LeetCode笔记:Biweekly Contest 89
- leetcode546_leetcode 5
- LeetCode周赛332,让我看看多少人大意翻车在了第二题?
- LeetCode——二叉树的非递归遍历