题目：
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
代码：
class Solution {
public:
bool isMatch(string s, string p) {
// both s and p reach their ends
if ( p.empty() ) return s.empty();
// p's next is not *
if ( p[]!='*' )
{
return ( s[]==p[] || (p[]=='.' && !s.empty()) ) && Solution::isMatch(s.substr(), p.substr());
}
// p's next is * and curr s match curr p
int i = ;
for ( ; s[i]==p[] || (p[]=='.' && i<s.size()); ++i)
{
if ( Solution::isMatch(s.substr(i), p.substr()) ) return true;
}
// p's next is * but curr s not match curr p
return Solution::isMatch(s.substr(i), p.substr());
}
};
tips:
这个代码在Leetcode最新接口上，是可以AC的。
思路有些复杂：主要判断下一个p是否是*，并分类讨论。
虽然代码AC了，但是有些疑惑的地方依然存在：
1. p[1]!='*' 这个语句是会遇到p[1]不存在（索引越界）的情况的，在我的mac上返回的结果是NUL，但是OJ可以通过。
2. p.substr(2)这个语句也会遇到与1同样的问题。
虽然OJ通过了，但是还有各种边界隐患。如果string索引越界了，应该是引发未定义行为，但是不知道为何能通过。增加了一个修正的版本，如下，对于p.size()==1的情况单独处理。
class Solution {
public:
bool isMatch(string s, string p) {
// both s and p reach their ends
if ( p.empty() ) return s.empty();
if ( p.size()== )
{
if ( s.empty() )
{
return false;
}
else
{
return ( s[]==p[] || p[]=='.' ) && Solution::isMatch(s.substr(), p.substr());
}
}
// p's next is not *
if ( p[]!='*' )
{
return ( s[]==p[] || (p[]=='.' && !s.empty()) ) && Solution::isMatch(s.substr(), p.substr());
}
// p's next is * and curr s match curr p
int i = ;
for ( ; s[i]==p[] || (p[]=='.' && i<s.size()); ++i)
{
if ( Solution::isMatch(s.substr(i), p.substr()) ) return true;
}
// p's next is * but curr s not match curr p
return Solution::isMatch(s.substr(i), p.substr());
}
};
这个版本是可以AC的，但自测的case还是有问题：
string s = "aaa"
string p = "c*a*b**"
对于连续两个*的就有问题，不知道是否是题意理解有误，不能出现连续两个*。
后续想清楚了，连续两个*属于非法输入，因为*相当于没有前驱节值了
===============================================================================
改用DP做一遍，看一下边界条件是否可以简化些。
代码：
class Solution {
public:
bool isMatch(string s, string p) {
const size_t len_s = s.length();
const size_t len_p = p.length();
bool dp[len_s+][len_p+];
// dp pre setting
dp[][] = true;
for (size_t i = ; i <=len_s; ++i) dp[i][] = false;for (size_t j = 1; j <=len_p; ++j)
{
if (p[j-]!='*')
{
dp[][j] = false;
}
else
{
dp[][j] = dp[][j-];
}
}
// dp process
for ( size_t i = ; i <=len_s; ++i )
{
for ( size_t j = ; j <=len_p; ++j )
{
if ( p[j-]!='*' )
{
dp[i][j] = ( s[i-]==p[j-] || p[j-]=='.' ) && dp[i-][j-] ;
}
else
// why p[j-2] and dp[i][j-2] not exceed the range?
// 'cause if a '*' occur, it must have a preceeding char
// So, j-2 is guaranteed non-negative
{
if ( dp[i][j-] || dp[i][j-] )
{
dp[i][j] = true;
}
else if ( dp[i-][j] )
{
dp[i][j] = s[i-]==p[j-] || p[j-]=='.';
}
else
{
dp[i][j] = false;
}
}
}
}
return dp[len_s][len_p];
}
};
tips:
DP的解法效率很高（8ms 9ms过大集合）。
大体思路：与递归算法类似，都是按照当前元素的下一个是否是*来分类讨论的。客观上dp效率更高，主观上个人觉得dp对于边界的界定更强。
1.关于dp[len_s+1][len_p+1]
这里定义了dp[len_s+1][len_p+1]的数组，dp[i][j]代表s[0~i-1]与p[0~j-1]是否匹配。
那么多了1个长度是干什么的呢？为了使得dp过程能进行下去，可以想象在s和p字符串前面都插入了一个空白字符。
因此dp[0][0]代表s和p都是空白的情况，自然也匹配（所以dp[0][0]=true）。在3.再说如何初始化dp[][]
2. 状态转移递推公式
这部分是dp的核心，先按照p的下一个元素是否是*来分类的
如果不是*，则需要dp[i-1][j-1] && s[i-1]==p[j-1] || p[j-1]=='.'
如果是*，则分以下三种：
a. 如果dp[i][j-1]==true，则证明不用这个‘*’也能给匹配了，则直接dp[i][j]=true
b. 如果dp[i][j-2]==true，则证明不用这个*,并且捎带脚把p[j-2]也给去了，还能匹配上，那就更是dp[i][j]=true
c. 如果dp[i-1][j]==true，则说明，加上这个*，能把s[0]~s[i-1]都匹配上；现在多了一个*，能不能匹配呢？再分两种情况：
c1. 如果p[j-2]==s[i-1]，则加上p[j-1]的这个*，就相当于多复制出来一个p[j-2]与s[i-1]对位，则dp[i][j]=true
c2. 如果p[j-2]=='.'，则加上p[j-1]的这个*，相当于由万能的‘.’衍生出来一个与s[i-1]相同的字符再与s[i-1]对位，则dp[i][j]=true
其余情况，则dp[i][j]=false;
这个过程可以看到，利用dp做这个题目比greedy算法要有优势。因为dp保存了每一*比较的结果，可以方便回溯；而greedy方法，一般只看当前的情况（如果要保存每一轮的教过，则灰常麻烦），本人一开始就试图用greedy方法，最后无奈放弃了。
3. dp[][]的初始化
再确定了dp的思路之后，为了要让dp过程能够起来，必须对dp状态进行初始化。我的逻辑顺序是，先确定dp的大体过程，然后再考虑如何初始化dp数组让过程起来。
考虑dp[][]定义多了一维（即s和p开头都多了一个空字符），因此需要初始化两种极端情况。
a. dp[i][0] 即s取前i个元素，p一个不取：显然都是false，不能匹配
b. dp[0][j] 即s一个不取，p取前j个元素:
b1. 如果p[j-1]!='*'，则必然无法都消除p[0~j-1]，至少留着了p[j-1]
b2. 如果p[j-1]=='*'，则*前面的p[j-2]可以被这个*消除了，如果再有dp[0][j]==dp[0][j-2]
至此，dp初始化完成，都可以跑起来了。
4 关于如何保证'j-2'这类下标不会越界
这个问题困扰了我一段时间。后来终于明白了，OJ中给出的case都是合法的：即只要出现*，则它前面必然要有不是*的某个字符。
这种合法性具体体现在两点：
a. p开头不会有*
b. p任何位置不会有连续的两个*
注意，但凡出现'j-2'这类下标的地方，都是需要向前回溯的；又因为，只有下一个元素是*的时候，才需要向前回溯；因此，j-2这类下标就无形中得到了保证，不会越界。（但这种保障是leetcode的test case保证的，实际中不一定行）
Dynamic Programming方法在这道题上非常恰当，因为Greedy显然不利于回溯，而这道题要处理的case还多，几乎都涉及到前一个状态，后一个状态。因此毫无疑问DP是最佳的选择。
最后记录几个参考的日志：
http://www.bubuko.com/infodetail-604758.html
http://www.makuiyu.cn/2015/01/LeetCode_10.%20Regular%20Expression%20Matching/
http://blog.****.net/yangliuy/article/details/43834477
================================================
第二次过这道题，对于其他的方法已经都忘记了，首先想到的就是dp；基本照着原来的代码重新记着写了一遍。
class Solution {
public:
bool isMatch(string s, string p) {
bool dp[s.size()+][p.size()+];
std::fill_n(&dp[][], (s.size()+)*(p.size()+), false);
dp[][] = true;
for ( int i=; i<=s.size(); ++i ) dp[i][] = false;
for ( int j=; j<=p.size(); ++j )
{
if ( p[j-]!='*' ){
dp[][j] = false;
}
else{
dp[][j] = dp[][j-];
}
}
for ( int i=; i<=s.size(); ++i )
{
for ( int j=; j<=p.size(); ++j )
{
if ( p[j-]!='*' )
{
dp[i][j] = dp[i-][j-] && (s[i-]==p[j-] || p[j-]=='.');
}
else
{
if ( dp[i][j-] || dp[i][j-] )
{
dp[i][j] = true;
}
else if ( dp[i-][j] )
{
dp[i][j] = p[j-]==s[i-] || p[j-]=='.';
}
else
{
dp[i][j] = false;
}
}
}
}
return dp[s.size()][p.size()];
}
};
（1）要按照p中当前是否是*讨论
（2）其余的都条件判断就是背一背吧