思路总结
刷LeetCode的时候看到这样一个问题，要求实现一个支持Unix的.和*匹配符的正则表达式模型。思考了一下发现自己居然从来没有这方面的知识储备，于是简单学习了一下，在此做一个记录。
我们知道通用的正则引擎一般是基于DFA来实现的，这是一个用来进行字符串处理、词法分析的利器。不过对于这个问题，显然无需引入如此复杂的算法，因为支持的操作符仅有两个，也就意味着存在的状态不会太复杂。
设匹配函数为isMatch(s, p)，s为指向目标串的指针，p为指向模式串的指针，首先考虑仅有.匹配符的模型。如果*s == *p，或者*p == '.'，则说明当前指针所指向的两个字符是匹配的，它们可以是本来就对应相等，也可以是被.通配。这样，我们的答案就是isMatch(s+1, p+1)，也就是说仅需要继续考虑后面是否匹配。
如果我们再引入*匹配符，那么按照规定，这个运算符必须要作用于前一个字符。也就是说，如果模式串中*p后面没有一个*，我们可以把这种状态当作不存在*匹配符的情况来处理。也就是上面所说的情况。而如果模式串中*p后面存在这个*，则表明当前的目标串字符*s以及其后的任意个字符，都有可能被*p这个字符所匹配到。
这个时候我们使用贪心策略来处理：由于s中的任意字符会被匹配，所以我们维持p指针不动，不断试图将*p与*s相匹配。这时候的匹配规则与上述是相同的，我们可以有*p == *s，或者*p == '.'也可以。先前已经说过，这次的*p可能匹配了任意个字符，也就是说我们每次匹配了一个字符，使得s缩短一点，就要检测一下剩下的s能否与剩下的p相匹配，也就是要查看isMatch(s, p + 2)，如果能够匹配就可以直接返回true。
但是，即便此时不能够匹配，也要一直尝试下去不断缩短s，因为说不定s再被匹配掉一个字符之后，剩下的就能够与p相匹配了呢。 这样一直尝试尽可能缩短s，直到最后不满足条件。这时候，我们仍要计算isMatch(s, p + 2)，不过此时的计算结果就可以作为最终结果返回了，因为我们已经用当前的*p匹配掉尽可能多的s了。
最后需要注意一个边界细节，即如果p为空，那么当且仅当s为空时才能返回true，其意义是显然的。
示例代码
class Solution {
public:
bool isMatch( const char *s, const char *p )
{
if ( *p == 0 ) return *s == 0;
if ( *(p + 1) != '*' ) {
if ( *s == *p || (*p == '.' && *s != 0) ) {
return isMatch( s + 1, p + 1 );
} else {
return false;
}
} else {
while ( *s == *p || (*p == '.' && *s != 0) ) {
if ( isMatch( s, p + 2 ) ) return true;
s++;
}
return isMatch( s, p + 2 );
}
}
};