Regular Expression Matching
Implement regular expression matching with support for'.'
and'*'
.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
为什么最后一个会匹配呢?原因是:'*' Matches zero or more of the preceding element.这个条件;
这个条件很容易忽略,也是最重要的条件了,因为这个相当于*可以把它的前缀字母”吃掉“;我就栽在这里了。
所以也是为什么我们需要“往前看”,看到pattern字符串后一位,假设这个字符串为const char *p; 那么我们就要先考虑到前一个指针,然后再比较当前指针。
下面代码来自:
http://leetcode.com/2011/09/regular-expression-matching.html
class Solution {
public:
bool isMatch(const char *s, const char *p) {
if (*p == '\0') return *s == '\0';
// next char is not '*': must match current character
if (*(p+1) != '*') {
return ((*p == *s) || (*p == '.' && *s != '\0')) && isMatch(s+1, p+1);
}
// next char is '*'
while ((*p == *s) || (*p == '.' && *s != '\0')) {
if (isMatch(s, p+2)) return true;
s++;
}
return isMatch(s, p+2);
}
};
但是文中只是分析了原理,并没有分析各个代码的作用和如何实现的,所以,我这里就分析一下他的代码。
因为程序非常短,所以每一句都有非常重要的意义,看仔细了,漏掉任何一个细节都理解不了这个程序。
if (*p == '\0') return *s == '\0';
//if (*s == '\0') return *p == '\0';
不能增加后面一句,因为*(p+1) = '*'的时候,是可以吃掉*p的。
// next char is not '*': must match current character
if (*(p+1) != '*') {
return ((*p == *s) || (*p == '.' && *s != '\0')) && isMatch(s+1, p+1);
}
这里是向前判断,不能判断*p,同样道理因为*可以吃点前一个字母。满足条件就递归。
// next char is '*'
while ((*p == *s) || (*p == '.' && *s != '\0')) {
if (isMatch(s, p+2)) return true;
s++;
}
*(p+1)=='*'的时候;判断当前*p的值如果等于*s或是*p=='.'的情况,就可以跃过当前p和p+1的值,直接在p+2的位置开始重新进行递归比较。
p+2位置之后的字符串可以和s串的s, s+1,s+2...等位置开始的子串匹配,如果匹配成功都可以。
return isMatch(s, p+2);
最后一句也非常重要,就是如果p+2开始的子串和s,s+1,s+2等所有子串都不匹配的时候,就吃掉这个*,就是这个时候把*当做是0个*p使用。
这也是为什么无需要判断*p==*s这个条件的原因。
然后就回溯,原文中提到的所谓回溯法就在这句体现出来了!够精巧吧!
2014-2-22 update
好困难的题目,主要是要考虑s为空的情况,这样就比较难处理了。
不过终于被我征服了(彻底理解了)。
我上面的分析有一定道理,不过感觉当时还是理解的不是那么透切。留着参考吧。
下面是我自己写的代码:和上面的程序,效率是一样的,不过递归处理有点不一样。
//2014-2-22 update
bool isMatch_3(const char *s, const char *p)
{
if (!*p) return !*s;
for ( ; (*s && *p) && *(p+1) != '*' && (*s == *p || *p == '.'); s++, p++);
if (!*s && !*p) return true;
if (!*p || *(p+1) != '*') return false;
//if (!*s) return isMatch(s, p+2);有了下面的return isMatch(s, p+2),那么就不需要这句了。主要是处理特例:s为空,p == "c*d*g*"等字符串
while (*s)
{
if (isMatch(s, p+2)) return true;//这就相当于先序遍历了
if (*p != '.' && *p != *s) return false;
s++;
}
return isMatch(s, p+2);//为什么是isMatch(s, p+2)而不是!*(p+2)?因为当s进入循环,然后s == ''空的时候,那么就需要继续递归判断
}
分享到:
相关推荐
LeetCode leetcode部分题解答代码实现
leetcode 上面题目的解决代码,可以查找对应的题目答案,基本上都有了
leetcode 平台题目实现代码 翻译版PDF高清版 电子书 个人收集电子书,仅用学习使用,不可用于商业用途,如有版权问题,请联系删除!
leetcode常用算法java代码
LeetCode151道题,面试过程中的积累,有个人理解和解释。有的包含多种实现方法。
第一题的四种方法,包括暴力破解和字典、列表。我也是刚开始练习
leetcode刷题记录,包含代码和思路讲解,非常详细
leetcode(含python、java、c)代码合集,目录清晰,适合刷leetcode的朋友参考
这里提供我刷LeetCode前400题的代码全解,部分题目还提供了2-4种解法,对于刷题的你,想必会很有帮助!
leetcode题库 my-leetcode-code leetcode代码管理 此代码列表为本人在leetcode目前已解决题库代码 代码环境为python3
LeetCode 44. Wildcard Matching Wildcard Matching O(N) by Jimbowhy http://blog.csdn.net/WinsenJiansbomber/article/details/50862569 在 LeetCode 上看到第二个有趣的问题,是关于字符串匹配的,在接触过正则...
使用python对LeetCode题库进行解答。
LeetCode 的解题代码和中文讲解
本仓库主要用于维护LeetCode刷题过程中的代码笔记和解题思路,欢迎大家共同维护,仓库文档 内容说明 本仓库的题目主要以题目标签作为划分标准,这里可以和LeetCode做对比。 FAQ 项目代码规范说明 涉及项目结构说明...
leetcode中国 LeetCode LeetCode 在线评测网站解题代码! Here is a for each problem, which I got from the Internet and is very useful. Chinese leetcode .
Leetcode cookbook算法集+源代码
leetcode 周赛难度力码 的代码参考。 当然,我也会每周更新一些关于这些问题的注释,但不是全部。 欢迎开 issue 讨论! 要求 Xcode C++ 11 问题 清单(链表) ID 标题 困难 解决方案 笔记 2 中等的 19 中等的 21 简单...
leetcode 答案力码 leetcode 的答案代码
LeetCode:LeetCode的代码
Leetcode:LeetCode解题代码