首页 > 代码库 > 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); } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。