problem：
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") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "a*") → trueisMatch("aa", ".*") → trueisMatch("ab", ".*") → trueisMatch("aab", "c*a*b") → truethinking：
吐槽几句：
字符串匹配，’.’和’*’的意义很简单，不用陈述，但：
isMatch("aab", "c*a*b") → true
算哪门子事？
leetcode （）已有好多人在争论，这C*是不是可以代表0个C，我TM无语了。
最后的感觉就是这道题为了宣传那个特定的算法而把条件改了？
所以，我个人把这个扯淡的条件判定为错误。
（1）没有*的情况很好解决，难在怎么处理*
（2）比如ABBC与 A*C、A*BC，，很清楚，利用深搜的思想，只要把BB与*、*B整体作匹配就OK了
自己写了个测试程序，官方的那个扯淡条件通不过
#include <iostream>#include <memory.h>using namespace std;class Solution {public:bool isMatch(const char *s, const char *p) {int n=0;int m=0;int index=0;while(*(s+n)!='\0'){n++;}while(*(p+m)!='\0'){m++;}// cout<<"n: "<<n<<"m: "<<m<<endl;if(n==0||m==0)return false;int *a = new int[m];memset(a,0,sizeof(int)*m);if((*p=='.')||(*p==*s)){a[0]=1;index++;}for(int i=1;i<m;i++){if(a[i]==1)continue;while(index<n){if(*(p+i)=='.'){a[i]=a[i-1]&0x01;index++;}else if(*(p+i)=='*'){int tmp_s=1;int tmp_p=1;while((*(s+index)==*(s+index+tmp_s))&&(index+tmp_s<n)){tmp_s++;}while((*(s+index)==*(p+i+tmp_p))&&(i+tmp_p<m)){tmp_p++;}if((index+tmp_s==n-1)&&(i+tmp_p==m-1)){a[i+tmp_p]=a[i-1]&0x01;index+=tmp_s;break;}else{for(int j=0;j<tmp_p;j++){a[i+j]=a[i+j-1]&0x01;index+=tmp_s;}}//else}//else ifelse{if(*(s+index)==*(p+i)){index++;a[i]=a[i-1]&0x01;// cout<<"i: "<<i<<"a[i]:"<<a[i]<<endl;}else{a[i]=a[i-1]&0x00;return false;}}//elseif(i==m-1)break;}//while}//forif(index<n)return false;elsereturn a[m-1];}//isMatch};int main(){char *s="aab";char *p="aa";Solution mysolution;cout<<mysolution.isMatch(s,p)<<endl;}我测试了几组，通过了，欢迎找BUG。
贪婪是最真实的贫穷，满足是最真实的财富
