首页 > 代码库 > leetcode第一刷_Regular Expression Matching

leetcode第一刷_Regular Expression Matching

这道题跟有?和*的那道题很像,不过要简单一些。为什么会简单呢,因为*号只能匹配跟它前面相同的字符。需要注意一点,从aab可以用c*a*b来匹配可以看出,*号可以使他之前的那个字符出现次数变成0。

昨天实验室的同学正好在做这个题,说想用递归做,我想都没想就说用递归肯定超时了。她为什么,我跟人家说因为递归的分支太多了,可怎么也想不起当初自己是怎么写的,回来一看,居然用递归做的,打脸啊。。这个题为什么用递归可以呢?我觉得主要是因为*号的匹配规则,比起可以匹配任意字符来说,只能匹配之前的那个字符显得严格多了,很多分支都被剪掉了。

好,确定了整体的思路是递归,那具体怎么做?想一下递归的分支是怎么走的。同样的,两种符号中,‘.’对我们是不构成威胁的,之所以有很多种情况,是因为*,我们就可以按照*来划分,那是不是按照当前位置是不是*来划分呢?no no no,因为*匹配的是前面的那个字符,因此应该在它前面的那个字符的位置就可以考虑* 的问题,按照当前位置的后一个字符是不是*来划分是个不错的选择。

假设当前位置是i,假设i+1位置不是*,那么i位置必须完全匹配,这里的完全匹配分两种情况,要么是字符相同,要么p[i]=‘.‘。注意‘.‘必须是跟实际的字符相匹配的,不能匹配‘\0‘。如果i+1位置是*,分支情况就来了,如果当前位置是不匹配的,那么只能用这个*来讲p[i]的出现次数变成0,也就是继续匹配p+2的位置。如果当前位置是匹配的,那么既可以用p[i]匹配多次(此时之更新s的指针),也可以跳过这个字符(分支通过匹配p+2)。

写成代码会很简介:

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+1) != ‘*‘){
            return (*s==*p||(*p==‘.‘&&*s != ‘\0‘))&&isMatch(s+1, p+1);
        }
        while(*p==*s || (*p==‘.‘&&*s!=‘\0‘)){
            if(isMatch(s, p+2)) return true;
            ++s;
        }
        return isMatch(s, p+2);
    }
};