leetcode 10. 正则表达式匹配

leetcode 10. 正则表达式匹配

这道题最初刷题连答案都看不懂,实在不是一道容易的题目。

补充两个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和难以理解

 

上一篇:十一、VueJs 填坑日记之使用Amaze ui调整列表和内容页面


下一篇:使用U2net+cpu+pytorch完成照片素描化