首页 > 代码库 > leetcode第一刷_Wildcard Matching
leetcode第一刷_Wildcard Matching
又好又难的题。
我发现难题一般都包含了好几个简单题,必须对一些基本的算法熟练掌握才能快速准确的写出代码。这个题就用到了kmp,这个算法写过好多遍,还是不断的出错,哎。
题目中有两种符号,?可以匹配任意单个字符,*可以匹配任意0个或多个字符。?其实没什么,麻烦就麻烦在*上。一个*实际上代表了一段任意的字符串。很容易想到的一种解法是用递归,当p[i]不为*时,看p[i]是不是‘?‘或者p[i]==s[j],这样就把两个串都往下移一个位置,如果p[i]是*的话,一种情况是*代表的是0个字符,那么就只移动p,也可以代表多个字符,一步一步的移动s,代码如下,这种方式是正确的,小规模的数据是可以过得,但是大规模的会超时,因为有*之后支路实在是太多了。
class Solution { public: bool isMatch(const char *s, const char *p) { if (s == NULL || p == NULL) return false; if (*p == ‘\0‘) return *s == ‘\0‘; if (*p == ‘*‘) { while (*p == ‘*‘) ++p; while (*s != ‘\0‘) { if (isMatch(s, p)) return true; ++s; } return isMatch(s, p); } else if ((*s != ‘\0‘ && *p == ‘?‘) || *p == *s) { return isMatch(s + 1, p + 1); } return false; } };下面介绍一种很巧妙的思路。*可以代表任意一个字符串,那么如果将p按照*来分割的话,剩下的每一段都应该是s的子串,这些子串是有先后顺序的,中间其实是由*来连接的。如果这些子串却是按照顺序匹配了s,那么加上*之后,p和s就会完全匹配。这里有两个边界情况,第一个是如果p的开头不是*,那么分割后p的第一串必须跟s从头开始匹配,不匹配直接返回false。第二个边界是最后一段,如果p的最后一段不是*,那么p的最后一段必须与s的后半部分匹配。
实现的时候,p按照*分割没什么,一个字符一个字符的加就行了,如果是java的话一个split函数就搞定了,注意多个*连在一起的话相当于一个。判断一个字符串是不是子串我用的是kmp,有一个地方特别注意,q[0]=-1而不是0,j的初值也是-1,这里总是搞错。kmp算法的思想是让子串不断的匹配长串,如果子串在位置i出现不匹配的情况,则子串回到前面的某个位置q[i],这个位置使得p[0, q[i]]依然与长串匹配,且q[i]最大。有关kmp可以找matrix67的那篇博客,很精彩的。再加上边界条件的讨论,就可以写出完整的代码了。
我在变量命名的时候犯了个地级错误,但是编译运行是没有问题的,一个算法写到将近100行。。
class Solution { public: int p[100000]; vector<string> mp; bool bs = false, be = false; void getp(string &c){ p[0] = -1; int j=-1, i=1; while(i<c.length()){ while(j>=0&&c[j+1]!=c[i]&&c[j+1]!=‘?‘) j=p[j]; if(c[j+1] == c[i] || c[j+1] == ‘?‘) ++j; p[i] = j; ++i; } } int isSubstr(const char* a, string &b){ getp(b); int i=0, j=-1; while(a[i]){ while(j>=0&&b[j+1]!=a[i]&&b[j+1]!=‘?‘) j=p[j]; if(b[j+1] == a[i]||b[j+1] == ‘?‘) ++j; if(j == b.length()-1) return i+1; ++i; } return -1; } void partS(const char *p){ string tps; while(*p){ while(*p == ‘*‘) ++p; tps = ""; for(;*p&&*p!=‘*‘;++p) tps += *p; if(tps != "") mp.push_back(tps); } } bool fullcomp(const char *s, string &p, int len){ for(int i=0;i<len;i++){ if(s[i] != p[i] && p[i] != ‘?‘) return false; } return true; } bool isMatch(const char *s, const char *p){ if(s==NULL && p==NULL) return false; if(*p == ‘\0‘) return *s == ‘\0‘; mp.clear(); int i=0, j=0, l1=0, l2=0; while(s[i]) {++i; ++l1;} while(p[j]) {++j; ++l2;} partS(p); if(mp.size() == 0){ return true; } bool firstmatch = false; int offset = 0, tpoff; if(*p != ‘*‘){ if(mp.size()==1 && p[l2-1] != ‘*‘){ if(l1 > l2 || l1==0) return false; } if(l1<mp[0].length()||!fullcomp(s, mp[0], mp[0].length())) return false; offset += mp[0].length(); firstmatch = true; } vector<string>::iterator it=mp.begin(); if(firstmatch) ++it; for(;it!=mp.end()&&offset<l1;++it){ if(l1-offset<(*it).length()) return false; tpoff = isSubstr(s+offset, *it); if(tpoff == -1) return false; offset += tpoff; } if(it!=mp.end()){ return false; } if(p[l2-1] != ‘*‘){ for(int i=0;i<mp[mp.size()-1].length();i++){ if(p[l2-i-1] != s[l1-i-1] && p[l2-i-1] != ‘?‘) return false; } } return true; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。