class Solution {
    //动态规划，点评dp[i][j]表示字符串s的前i个字符能否与字符串p的前j的字符串实现正则表达式匹配
  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 = 1; i <= n; i++) {
            if (p.charAt(i-1) == '*') {
                dp[0][i] = dp[0][i-2];
            }
       }
       for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '.' || p.charAt(j-1) == s.charAt(i-1)) {
                dp[i][j] = dp[i-1][j-1];
            } else if (p.charAt(j-1) == '*') {
                dp[i][j] = dp[i][j-2] || ((s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == '.')&&dp[i-1][j] );
                // 匹配0次，匹配多次
            }
        }
       }
       return dp[m][n];
    }
}