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") → true 注意*表示前一个字符的个数，可以为0. 动态规划的一题：扫描到s的第i个字符和p的第j个字符时状态的确定：当p当前扫描到的第j个字符字符不为‘*’时，判断p当前的字符和s当前的字符是否匹配，如果匹配则置true，否则置false；               当p当前扫描到的第j个字符为‘*’时，如果i-1之前的字符和j之前的字符能匹配且s的第i个字与p的j-1个匹配，则置true                                            否则如果s的前i个字符和p的前j-1个字符或p的前j-2个字符匹配，则置true；

1 public class Solution { 2     public boolean isMatch(String s, String p) { 3         int m=s.length(); 4         int n=p.length(); 5         boolean dp[][]=new boolean[m+1][n+1]; 6         dp[0][0]=true; 7         for(int i=1;i<=m;i++){ 8             dp[i][0]=false; 9         }10         for(int j=1;j<=n;j++){11             if(p.charAt(j-1)!='*')12              dp[0][j]=false;13              else{14                   dp[0][j]=dp[0][j-2];15              }16       }17       18       for(int i=1;i<=m;i++)19       for(int j=1;j<=n;j++){20           if(p.charAt(j-1)!='*'){21               if(dp[i-1][j-1]&&(s.charAt(i-1)==p.charAt(j-1)||p.charAt(j-1)=='.')) 22               dp[i][j]=true;23               else dp[i][j]=false;24               25           }else{26               if(dp[i-1][j] && (s.charAt(i-1) == p.charAt(j-2)||p.charAt(j-2)=='.'))dp[i][j]=true;27               else   if (dp[i][j-1]||dp[i][j-2]) dp[i][j]=true;28               else dp[i][j]=false;29           }30       }31       32       return dp[m][n];33            34     }35 }