当前位置 博文首页 > Regular Expression Matching_让代码改变世界：LeetCode 10
又两天没更新了，这两天倒不是偷懒了，而是遇到了一个难题，这两天一直在思考这个问题，今天做一个了结吧。
这是leetcode的第10题，难度为hard，是leetcode里难度等级最大的题目了，由于上一道hard的题做的不是很理想，所以打算多花写时间把这道题搞定，但事与愿违，两天的时间投入也没有通过测试，到后来只能放弃了。不过放弃到不是因为花的时间多了或者说编得烦了之类的，而是因为当时的代码已经将近200行了，而没有运行还是有各种“补丁”错误。怎么说呢，算法大致思路用了大约不到一天时间，而“打补丁”的时间已经超出了算法设计和编码时间，也就是说，即便再经过几天努力，程序通过了调试，那也是补丁上套补丁了，甚至一些bug还没有测试出来，这种情况下选择放弃是因为这不是努力不努力的问题了，因为很显然，算法设计的是错的!正确的算法时不会打很多补丁的，更不应该是试凑出来的。说了这么多，只是想说明，这个东西如果算不出来肯定是算法没学好，并不是你不够努力活着编程语言没学好，找到问题的关键才是解决问题的前提。
废话不多说了，上题吧
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
这个题目学过Linux系统的人会比较熟悉，当然其他地方也会见到。正则表达式是一种很有用的工具，这道题考察的就是实现其中的一些匹配机制。当然只是其中一小部分，就算你没听过正则表达式也是可以理解题意的。这里有问题的可能是"ab"和“.*”这两个为什么能匹配，这是题意理解的一个问题，'*'可以匹配前面的0个或多个字符，这句话是针对后面的串说的，也就是说“.*”中的"*"可以匹配前面的0个或多个“.”，而不是“.”实例化以后的字符，说的更直白一点儿，就是“*”可以当多个"."使用。
理解了题意就来说一下我的错误思路吧，之所以说是因为我并没系统学过算法课程，我的解题思路应该是可以代表这一部分人的，通过分析我的错误，希望大家可以找到属于自己的“正确答案”。
两个字符串，比较它们的“相等”关系，这两点直接把我引到了一一匹配的解题思路中，也就是把比较字符串相等的思路迁移到这里来，而把那些匹配的东西当做特殊情况来剔除。这样一来首先我想到了（其实也花了很长时间）".*"的特殊性，想先通过这个来分解字符串，然后进一步在用"*"来分解。。。这些就不多说了，前面已经说明，这种方法是错误的，很难得到正确解决，调试的过程就像是在救火，哪儿着了就跑去哪儿浇水，有时甚至不知道是哪儿着了。
说别的也没啥用了，直接上大神的代码吧（在这里感谢dong.wang.1694的代码分享和详细解答）
</pre><pre name="code" class="cpp">class Solution {
public:
bool isMatch(string s, string p) {
int sSize = s.size(), pSize = p.size(), i, j;
bool checked[sSize+1][pSize+1];
// fill_n(&matched[0][0], (sSize+1)*(pSize+1), false);
for(j=2, checked[0][0]=true, checked[0][1]= false; j<=pSize; ++j) // match s[0..0]
checked[0][j] = p[j-1] == '*'? checked[0][j-2] : false;
for(i=1; i<=sSize; ++i)
for(j=1, checked[i][0]=false; j<=pSize; ++j)
{
if(p[j-1]=='*') // case (1)
checked[i][j] = (j>1) && ( checked[i][j-2] || ( ( checked[i-1][j]) && (s[i-1]== p[j-2] || p[j-2] == '.')) );
else // case (2)
checked[i][j] = checked[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');
}
return checked[sSize][pSize];
}
};算法的核心是要构建一个二维表，表明叫checked。表中存的都是二进制数1或者0(true或者false)。那checked[i][j]也就是表中的第i行j列是1或者0代表什么呢？它代表s[0]—s[i](不含s[i]，即s中前i个元素)和p[0]—p[j](含义同前)，是否匹配成功。举个例子说吧，加入s="aab",p="c*a*b"那checked[2][3]就是说"aa"和"c*a"是否匹配，显然这个是不匹配的，即checked[2][3]=0，类似可知checked[2][4]=1，总之就是这么个意思。
很容易得到，checked[s.size()+1][p.size()+1]的值就是要返回的答案。那么接下来就是填这个表了，我们从头开始说：
（1）首先，我们先填表的第一行，也就是checked[0][j](j=0,1,...)。那么第一就是checked[0][0]了，通过checked[i][j]的含义很容易得到checked[0][0]=1(两个空串肯定是相等了)，类似可知checked[0][1]=0(一个字符不可能和空串匹配上)。到这里我们可以知道，checked[0][j]其实就是说p中前j个元素是否与空串匹配。前面两个已经知道了，我们从第三个及以后的开始（假设就是前j个，注意其下标为j-1），这个还得分两种情况：如果p[j-1]==‘*’，那么这个'*'可以把前面的一个给消去（因为可以表示0个前面的字符嘛）,消去以后那其真值就和消去前面的那个真值一样了，也就是checked[0][j]=checked[0][j-2];如果p[j-1]!=‘*’，那显然，最后这个p[j-1]是无法消去的，那么它也就不肯能和空串匹配了，即checked[0][j]=false;这样类推到结束可以得到表的第一行。
（2）然后，我们填表的第一列。（这种根据规律填表的算法一般都是先通过分析边界输入把表的边缘填好的）第一列中第一行已经填好了，下面的也比较简单，因为checked[i][0]表示p为空串时，s是什么时可以匹配，显然，只有s中有字符那就不能匹配,所以i>0时checked[i][0]全部为0，即表的第一列除了第一行为1外全部为0。
（3）最后，我们就要找出最后的checked[i][j]的填写规律了。和填写checked[0][j]时一样，我们还是分两种情况考虑：如果p[j-1]==‘*’，那情况有两种，一种是消去了前面的字符，即checked[i][j]=checked[i][j-2]，这种情况是说把“*”前的字符消去了，那剩下的部分是否匹配就取决于以前的是否匹配了。二一种是没有消去，把“*”用上以后也可能是匹配的，这种情况下“*”充当了一个或者多个字符，但具体是多少我们不得而知，所以这时不能在判断checked[*][j-2]了，因为你不知道“*”充当了多少字符，你把它去掉后对应前面的匹配位置是不知道的。这么说不知大家能不能理解，就比如说吧，s="abbbbbbbbc"，p="ab*c"显然这两个串是匹配的，但是在填表过程中当j指向c时，如果把“b*”去掉，那么剩下的一个a只能跟s第一个匹配，而中间的b有多少是不知道的，也就是说checked[*][j-2]中的*不知道是i减去多少得到的。总之，“*”必须留下，也就是说要判断checked[*][j]，我们从另一个角度来考虑填表问题，即按列填表，这样一来也就是说p是固定的一个结尾为“*”的字符串且已知“*”充当了至少一个字符，然后让s中的字符一个一个增加，看是否能与p匹配，显然只有当增加的字符为“*”可代替字符时才是匹配的，而前一个正好是checked[i-1][j]，也就是说增加第i个数据前两个是匹配的，且增加的字符是“*”可代替的（s[i-1]==p[j-2] || p[j-2]=="."）。这一点说得有点儿多了，下面说最后一个字符不是“*”的情况，这个情况就比较简单了，最后增加了一个“实体”那显然增加的这个实体要和s中最后一个匹配且在增加实体前面它是匹配的。
后面那个checked[i-1][j]处可能不大好理解，大家多想一下按列填表以及为什么不能按行就可以了，这个确实有难度。
然后说点儿什么呢，说点儿做题的感受吧。本人自认为智商还是可以的，平时也好钻研这种题目，但怎么说呢，毕竟不是计算机专业的学生，没有学过算法设计的理论，完全凭自己一腔热血在做题。这样跟专业的还是有很大差距的，值所以说这些话是告诉大家找对学习的方向，要想做好算法，还是要静下心来学习一下算法理论的。凭借自己的小聪明不会走得太远的，我现在就已经开始看算法一类的书了。当然，要学的东西是太多了，大家找好自己的方向，多多努力就好。
今天心情依然不是很好，但很庆幸自己没有堕落而是坚持在写这些东西，希望有一天能实现自己的梦想。也祝每一个坚持的人实现自己的梦想。
