class Solution {public:	bool judge(char a,char b)	{		if(a==b||b=='.')			return true;		return false;	}    bool isMatch(string s, string p) {        int n=s.length();        int m=p.length();        int idx=0;        bool dp[1008][1008];        memset(dp,false,sizeof(dp));        dp[0][0]=true;        for(int i=0;i<=n;i++)        	for(int j=1;j<=m;j++)        	{        		if(p[j-1]=='*'&&j-2>=0)        		{        			if(dp[i][j-2])        				dp[i][j]=true;        			if(i>0&&dp[i-1][j]&&judge(s[i-1],p[j-2]))        				dp[i][j]=true;				}				else				{					if(i>0&&dp[i-1][j-1]&&judge(s[i-1],p[j-1]))						dp[i][j]=true;				}			}		return dp[n][m];	}};

参考思路：

 to see which companies asked this question

 

This problem has a typical solution using Dynamic Programming. We define the state P[i][j] to be true if s[0..i) matches p[0..j)and false otherwise. Then the state equations are:

1. P[i][j] = P[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
2. P[i][j] = P[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
3. P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if p[j - 1] == '*' and the pattern repeats for at least 1 times.

这样的动态规划可以这样理解：

用正则表达式p匹配s，要求两个串都匹配完，现在要进行状态转移

如果是字符或'.'，显然只要按照正常的匹配方式即可

’*‘和它之前的字符却有多种匹配方式：一个也不匹配，或者匹配它所有能匹配的字符。这时只要之前的状态是可行的，那么当前状态就是可行的

总的来说是个比较难想的分类讨论。当然还有递归的方式解决这个问题啦