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

DP的思想跃然纸上啊，注意分情况讨论即可。

注意下面代码中  当 p[j-1] == '*' 的时候的判断比较烦，有几种情况是为true的，最后那个括号里的判断没有的话是不能AC的，为了解决的情况是比如

aa 要和a*匹配，括号里的意思是既然另一个子串是*，那么判断再多一个*前的那个字符能不能把我也匹配了。

LeetCode的用例还是比较简单，没有两个子串都有*的情况。

class Solution {
public:
 bool isMatch(const char *s, const char *p) {
 // Start typing your C/C++ solution below
 // DO NOT write int main() function 
 if ( !s || !p )
 return !s&&!p;
 int ns=strlen(s);
 int np=strlen(p);
 vector<vector<bool> > dp(ns+1,vector<bool>(np+1,0));
 dp[0][0]=true;
 for(int i=1;i<=ns;i++)
 if ( s[i-1]=='*' )
 assert(i>=2);
 dp[i][0]=dp[i-2][0];
 for(int j=1;j<=np;j++)
 if ( p[j-1]=='*' )
 assert(j>=2);
 dp[0][j]=dp[0][j-2];
 for(int i=1;i<=ns;i++)
 for(int j=1;j<=np;j++)
 if (s[i-1]=='.'||p[j-1]=='.')
 dp[i][j]=dp[i-1][j-1];
 else if ( s[i-1]=='*')
 dp[i][j]=dp[i-1][j]||dp[i-2][j];
 else if ( p[j-1]=='*')
 dp[i][j]=dp[i][j-1]||dp[i][j-2]||(dp[i-1][j]&&(s[i-1]==p[j-2]||p[j-2]=='.'));
 else
 dp[i][j]=dp[i-1][j-1]&&s[i-1]==p[j-1];
 return dp[ns][np];

Wildcard Matching：

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
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", "*") ? true
isMatch("aa", "a*") ? true
isMatch("ab", "?*") ? true
isMatch("aab", "c*a*b") ? false

思路是一样的，但是这个要比上一个简单一点。还是注意当 p[j]=='*'的时候。

但是大数据的时候，这回O(n2)的这个算法居然不给过了~ 空间溢出，不知道怎么设的~那就逼俺们写个递归的呗～

class Solution {
public:
 bool isMatch(const char *s, const char *p) {
 // Start typing your C/C++ solution below
 // DO NOT write int main() function
 if (!s||!p)
 return !s&&!p;
 int na=strlen(s);
 int nb=strlen(p);
 vector<vector<char> > dp(na+1,vector<char>(nb+1,0));
 dp[0][0]=1;
 for(int i=1;i<=na;i++)
 if(s[i-1]=='*')
 dp[i][0]=dp[i-1][0];
 for(int j=1;j<=nb;j++)
 if(p[j-1]=='*')
 dp[0][j]=dp[0][j-1];
 for(int i=1;i<=na;i++)
 for(int j=1;j<=nb;j++)
 if (s[i-1]=='?'||p[j-1]=='?')
 dp[i][j]=dp[i-1][j-1];
 else if(s[i-1]=='*')
 dp[i][j]=(dp[i-1][j]||dp[i-1][j-1])?1:0;
 else if (p[j-1]=='*')
 dp[i][j]=(dp[i][j-1]||dp[i-1][j-1]||dp[i-1][j])?1:0;
 else
 dp[i][j]=(dp[i-1][j-1]&&s[i-1]==p[j-1])?1:0;
 return dp[na][nb];
 class Solution {
public:
 bool isMatch(const char *ss, const char *sp) {
 // Start typing your C/C++ solution below
 // DO NOT write int main() function
 if (!s || !p )
 return !s&&!p;
 else if ( *s=='\0' || *p=='\0' )
 const char* end=*s=='\0'?s:p;
 const char* oth=end==s?p:s;
 int i=0;
 for(;oth[i]!='\0';i++)
 if (oth[i]!='*')
 break;
 return oth[i]=='\0';
 else if ( *s=='?' || *p=='?' )
 return isMatch(s+1,p+1);
 else if ( *s=='*' || *p=='*' )
 const char* star=*s=='*'?s:p;
 const char* oth=star==s?p:s;
 while(*star=='*'&&*star!='\0')
 star++;
 int i=0;
 for(;oth[i]!='\0';i++)
 if (isMatch(star,oth+i))
 return true;
 return isMatch(star,oth+i);
 else
 return *s==*p&&isMatch(s+1,p+1);

递归TLE了之后呢，我又倒回来想DP怎么再优化一下，后来发现Leetcode讨论区有这个题的讨论，发现人家的空间优化过后是O(n)的，原来是考虑到dp记录数组

的更新是一行一行来的，每次最多用到上一行，所以当然可以只用两行来滚动更新好了，大赞！！！！！！以前都没有想到过可以这样优化空间啊~ 一直以来

做题想的都是时间复杂度，空间复杂度很少去考虑的。回来把空间优化了，然后又发现多个连续的*****其实跟一个*是一样的，所以对原字符串预处理一下，

加了这个代码，结果现在变成了超时。。。

怎么想都想不通，优化后空间是O(n)，时间最坏也是O(n*m)啊，跟讨论区里不一样的吗？怎么会不过。。。

看了下超时的那个例子，原来是如果 s长度大于p的长度，要把这里剪枝了。。。反过来又讲一下，LeetCode里没有考虑两个子串都有*的情况。把这个剪枝加

上之后，终于AC了~ 呼~~~~~~ 蛮有收获的~ 

看来空间的优化一定要记住！！！

class Solution {
public:
 bool isMatch(const char *ss, const char *sp) {
 // Start typing your C/C++ solution below
 // DO NOT write int main() function
 if ( !ss||!sp )
 return !ss&&!sp;
 string s=simplify(ss);
 string p=simplify(sp);
 int na=s.length(); 
 int nb=p.length(); 
 if ( na <nb )
 int notStar=nb-count(p.begin(),p.end(),'*');
 if (na < notStar )
 return false;
 vector<vector<bool> > dp(2,vector<bool>(nb+1,false)); 
 dp[0][0]=1; 
 for(int j=1;j<=nb;j++) 
 if(p[j-1]=='*') 
 dp[0][j]=dp[0][j-1]; 
 for(int i=1;i<=na;i++) 
 int curRow=i%2;
 int preRow=(i+1)%2;
 dp[curRow][0]=dp[preRow][0]&&s[i-1]=='*';
 for(int j=1;j<=nb;j++) 
 if (s[i-1]=='?'||p[j-1]=='?') 
 dp[curRow][j]=dp[preRow][j-1]; 
 else if(s[i-1]=='*') 
 dp[curRow][j]=(dp[preRow][j]||dp[preRow][j-1]); 
 else if (p[j-1]=='*') 
 dp[curRow][j]=(dp[curRow][j-1]||dp[preRow][j-1]||dp[preRow][j]); 
 else 
 dp[curRow][j]=(dp[preRow][j-1]&&s[i-1]==p[j-1]); 
 return dp[na%2][nb]; 
 string simplify(const char *s)
 vector<char> oneStar;
 char pre='#';
 while(*s!='\0')
 if ( !(pre=='*'&&*s==pre))
 oneStar.push_back(*s);
 pre=*s;
 s++;
 return string(oneStar.begin(),oneStar.end());

最后贴一个讨论区里贪心写的算法，80ms过大数据。。。虽然我不知道为什么贪心是对的。。。

这个世界神人真是多啊。。。

class Solution {
public:
bool isMatch(const char *s, const char *p) {
 // Start typing your C/C++ solution below
 // DO NOT write int main() function
 if(!s && !p) return true;
 const char *star_p=NULL,*star_s=NULL;
 while(*s)
 if(*p == '?' || *p == *s)
 ++p,++s;
 }else if(*p == '*')
 //skip all continuous '*'
 while(*p == '*') ++p;
 if(!*p) return true; //if end with '*', its match.
 star_p = p; //store '*' pos for string and pattern
 star_s = s;
 }else if((!*p || *p != *s) && star_p)
 s = ++star_s; //skip non-match char of string, regard it matched in '*'
 p = star_p; //pattern backtrace to later char of '*'
 }else
 return false;
 //check if later part of p are all '*'
 while(*p)
 if(*p++ != '*')
 return false;
 return true;

--转自