Regular Expression Matching
字符串匹配的这个题，用递归方法,直接在原函数中实现。在检测字符串“ab”和“.*c”时，会出现Running time
error。考虑应该是越界的问题，但没看出问题在哪儿。代码如下：
class Solution {
public:
bool isMatch(string s, string p) {
int sl=s.size();
int pl=p.size();
if(sl==0)
return pl==0;
if(pl==0)
return sl==0;
if(sl==1){
if(s[0]==p[0] || p[0]=='.'&&pl==1)
return true;
else
return false;
}
if(pl==1){
if(s[0]==p[0] || p[0]=='.'&&pl==1)
return true;
else
return false;
}
if(p[1]=='*'){
while(s[0]==p[0] || p[0]=='.'&& sl>0){
if(isMatch(s,p.substr(2)))
return true;
s=s.substr(1);
}
return isMatch(s,p.substr(2));
}
else{
if(s[0]==p[0] || p[0]=='.'&& sl>0)
return isMatch(s.substr(1),p.substr(1));
return false;
}
}
};
看到的另一种方法，代码如下：
class Solution {
public:
bool isMatch(string s, string p) {
return matchHelper(s, p, 0, 0);
}
bool matchHelper(string& s, string& p, int i, int
j){
if(p[j]=='\0'){
return s[i]=='\0';
}
if( p[j + 1] != '*'){
return ((s[i] == p[j]) || (p[j] == '.' &&
s[i]!='\0')) && matchHelper(s, p, i + 1, j + 1);
}
while((s[i] == p[j]) || (p[j] == '.' &&
s[i]!='\0')){
if(matchHelper(s, p, i, j+2)) return true;
i++;
}
return matchHelper(s, p, i, j+2);
}
};
方法2是可以通过的，比较了一下，方法二是采用变换起始值的方法，而方法一则是采用截取字串的方法，判断条件则都是一致的。不太清楚错误出在什么地方，看到的朋友来讨论一下啊
查看4道真题和解析