这道题最初刷题连答案都看不懂,实在不是一道容易的题目。
补充两个C++知识:
1)string对象的.c_str() 返回一个c语言字符串指针 即const char* p类型的指针;
2)c语言字符串的末尾为‘\0’可以用 *p==0 判断是否到达末尾。
递归解法不断的对当前情况和之后的情况进行判断:
1)当前匹配字符串p为空,如果此时s为空则return true,s不为空则return false;
2)当前匹配字符串p不为空,那么对当前p和s进行匹配(不考虑下一位是否有*),结果为match
2.1)下一位有*时,a和b都有可能有正确的解:
a)如果正解在a中,即当前字符串应该出现0次,那么无论当前的match成功与否,return isMatch(s,p.substr(2));
b)如果正解再b中,即当前字符串至少出现1次,那么当前至少应该匹配成功,并且还要递归求解isMatch(s.substr(1),p.substr(1)),即return match&&isMatch(s.substr(1),p.substr(2));
2.2 ) 下一位没有*时,
a)如果当前匹配成功match==true,那么匹配下一个字符,即 if(match) return isMatch(s.substr(1),p.substr(2));
b)如果当前匹配失败match==false,那么不用匹配直接return false;
C++ 代码如下:
一)使用string对象不使用指针
class Solution { public: bool isMatch(string s, string p) { //情况1,加入p为空那么只要s为空那么得到true反之false if(p.empty()) return s.empty(); //计算当前对应字符的匹配first_match,p不为空,匹配当前第一个字符(不包含s为空而p为a*之类的情况,只探讨是否字母直接匹配和.匹配) bool match=!s.empty()&&(s[0]==p[0] || p[0]=='.'); //情况2,p当前长度大于2,而且下一个字符是*(p.length()>=2 && p[1]=='*') if(p.length()>=2 && p[1]=='*'){ // 2.1(*为0个的情况)当前对应位置字符不匹配即first_match==false,那么p当前字母为0个时还有匹配可能,即s和p.substr(2) //或者当前字符能匹配first_match=true但不合适因此也需要为0个,即s和p.substr(2) // 2.2(*为1个以上的情况)当前对应字符匹配 first_match==true,而且正确答案就在此,那么匹配s的下一个字符和当前p的字符(因为*代表任意多的情况 return isMatch(s,p.substr(2)) || match && isMatch(s.substr(1),p); }else{ //情况3,如果p只剩下1个,而这时 // 3.1 first_match==true,那么去决议s.substr(1)和p.substr(1) // 3.2 first_match==false,那么已经false,不用继续了 if(match) return isMatch(s.substr(1),p.substr(1)); else return false; } } };
缺点:递归过程中,需要不断的复制储存子串,因此时间消耗较多,几百ms
二)使用指针:
// 优化后递归的版本,通过传递指针省去不断的复制和存储 20ms class Solution { public: bool isMatch(string s, string p) { //string对象的.c_str()返回一个c字符串的指针,即const char * return isMatch(s.c_str(),p.c_str()); } bool isMatch(const char* s,const char* p){ //c字符串是以\0结尾的 if(*p==0) return *s==0; bool match=(*s!=0) && (*s==*p||*p=='.'); if(*(p+1)=='*'){ return isMatch(s,p+2)|| match&&isMatch(s+1,p); }else{ return match&&isMatch(s+1,p+1); } } };
缺点:使用指针,相对更容易出bug和难以理解