本题为困难题，看了很久才看懂，题目如下：
注意，*和前面的字符是一个整体，如果不进行匹配的话两个字符都可以去掉。
思路：1.两个序列进行匹配，而且它们还有递推的关系，都应该考虑使用动态规划
2.动态规划创建二维数组dp[i][j],但要注意应该比两个字符串长度多出一位，i和j为0表示空的情况，主要目的是为了方便创建dp数组的初始值
3.具体办法：
3.1.初始化，dp[0][0]=true,dp[0][j](j!=0)=false;很好理解
3.2.当遍历到i和j时，两者相等或p遍历到"."的位置，可以匹配，那么如果前一位也能匹配的话就为true
3.3.当j指向的是*时：分情况讨论：
3.3.1.s[i]!=p[j-1]，即*代表的字符不能与相应的i位匹配，那应该考虑去掉*和前面的字符，即匹配0次的情况，如下：
这个时候dp[i][j]=dp[i][j-2].
3.3.2.此时若s[i]==p[j-1]，即s[i]可以和*前面的字符匹配，这个时候就会出现到底应该匹配几次的问题，例如s="caaab",p="ca*ab"，此时i=j=3，我们的动态规划是从前往后遍历的，只能由前面的状态来推导，我们可以把i往前移动，一直到s[i]不等于p[j-1]，如果这里匹配不上的话，那么之后的匹配不可能成功，反过来，dp[i][j]的状态完全可以前推到s[i]不等于p[j-1]时的状态，由其决定。假设s[i1]!=p[j-1]，而i1到i之间的所有位都等于p[j-1]的话，从i1到j之间所有状态都由dp[i1][j]决定，所以dp[i][j]完全可以由dp[i-1][j]来决定，就算i-1和i位相等，那么最终状态肯定也是一样的。故dp[i][j]=dp[i-1][j]。如下：
代码如下：
class Solution { public boolean isMatch(String s, String p) { int m=s.length(); int n=p.length(); boolean[][] dp=new boolean[m+1][n+1]; dp[0][0]=true; for(int i=0;i<=m;i++){ for(int j=1;j<=n;j++){ if(p.charAt(j-1)=='*'){ dp[i][j]=dp[i][j-2]; if(match(s,p,i,j-1)) dp[i][j]=dp[i][j]||dp[i-1][j]; }else{ if(match(s,p,i,j)) dp[i][j]=dp[i-1][j-1]; } } } return dp[m][n]; } boolean match(String s,String p,int i,int j){ if(i==0) return false; return s.charAt(i-1)==p.charAt(j-1)||p.charAt(j-1)=='.'; } }