题目：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
思路：
牢记一点，题目中所讲preceding character 代表的是出现*字符的前面一个字符。
本题的一种思路是递归，容易理解，顺便讲下具体步骤：
对于s[0...i-1] p[0...j-1]
首先判断当前位置下一个字符是否是*，
如果是*，直接排除当前两个字符，递归调用下面的，如果递归调用返回false，再进行下一步，就是考虑preceding character，它指的是*之前的一个字符，接下来就看s下面的字符与之前的这个字符是否一样或者它本身就是 “.” 。这是一种情况。
对于第二种，下一个字符不是*，这种情况较为简单，如果当前比较的两个字符相同或者p中的字符是"."，返回true。
对于动态规划方法，其实思路一样，
首先考虑的是初始化问题，p中首字符一定不是*，暂且当成一个说明吧，不解释，我也解释不了。
对于字符不是*得，程序写的很清晰，不再赘述。
如果字符是*，就是判断之前两位，先考虑0个字符的
代码：
class Solution {
public:
//https://leetcode.com/problems/regular-expression-matching/
//记住 本题与wildcard matching不同的
/*bool isMatch(string s, string p) {
//if (s.empty()) return p.empty(); 不需要判断s是否为空，因为后面万一出现A*之类的，反正A可以算0次
//但是当p是空的时候，s一定要是空的
if (p.empty()) return s.empty();
if(p[1]!='*'){
if(p[0]==s[0]||(p[0]=='.'&&s[0]!=' ')){
//s不能结尾
return isMatch(s.substr(1), p.substr(1));
}else
return false;
}else{
if (isMatch(s, p.substr(2))) return true;////代表前面的字符出现0次 而且还算是迭代，方便后面继续出现***
int index=0;
while(index<s.size()&&(s[index]==p[0]||p[0]=='.')){
if(isMatch(s.substr(++index), p.substr(2))) return true;
}//这个时候先是让前面的一个字符出现一次,再是2次....
return false;
}
}*/
bool isMatch(string s, string p){
/*
f[i][j]==ifs[0...i-1] p[0...j-1]
*/
int m=s.size(),n=p.size();
vector<vector<bool> > f(m+1,vector<bool>(n+1,false));
//初始化 initialize
f[0][0]=true;
for(int i=1;i<=m;i++){
f[i][0]=false;
}
for(int i=1;i<=n;i++){
f[0][i]=i>1&&p[i-1]=='*'&&f[0][i-2];//因为此时是空的
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(p[j-1]!='*'){
f[i][j]=f[i-1][j-1]&&(p[j-1]==s[i-1]||p[j-1]=='.');
}else{
//p[0] 不能还*
f[i][j]=f[i][j-2]||( f[i-1][j]&&(p[j-2]==s[i-1]||p[j-2]=='.' ) );
// f[i][j]=f[i][j-2]|| f[i-1][j-2]&&p[j-2]==s[i-1] || f[i-2][j-2]&&p[j-2]==s[i-1]&&p[j-2]==s[i-2] ...
// f[i-1][j]=f[i-1][j-2]|| f[i-2][j-2]&&p[j-2]==s[i-2] || ....
//f[i][j] = f[i][j - 2] || ((s[i - 1] == p[j - 2] || '.' == p[j - 2]) && f[i - 1][j]);
}
}
}
return f[m][n];
}
};
//http://blog.csdn.net/u010025211/article/details/46841037