前言
现在发现能找到一段时间能安心的做自己的事情不被别人打扰是多么的舒服，现在终于有点时间记录下今天抽空理解的一个题目Regular Expression Matching,一开始看到题目难度为5,直接跳过，今天思考了下，能够理解怎么做的了，记录下～
题目
Regular Expression Matching
- 题目链接：http://leetcode.com/onlinejudge#question_10
- 题目思路：
- 字符串
const char *s和用于匹配的pattern，const char *p。我们需要关注的是p+1。 - 如果
*(p+1)不是'*',那么只有*p == *s或者*p == '.'(这时候*s不能为\0)的时候才可能继续匹配。 - 如果
*(p+1)为'*',对于s，依次比较*s和*(p+2),直到匹配或者不匹配。
- 字符串
- 实现：
bool isMatch(const char *s, const char *p) {
if (*p == '\0') return *s == '\0';
if (*(p+1) != '*') {
if (*p == *s || *p == '.' && (*s) != '\0') return isMatch(s+1, p+1);
return false;
} else {
while (*p == *s || *p == '.' && (*s) != '\0') {
if (isMatch(s, p+2)) return true;
s++;
}
return isMatch(s, p+2);
}
}