1
class Solution {
2
  public boolean isMatch(String s, String p) {
3
    if (p == null || p.length() == 0) return (s == null || s.length() == 0);
4

5
    boolean dp[][] = new boolean[s.length() + 1][p.length() + 1];
6
    dp[0][0] = true;
7
    for (int j = 2; j <= p.length(); j++) {
8
      dp[0][j] = p.charAt(j - 1) == '*' && dp[0][j - 2];
9
    }
10

11
    for (int j = 1; j <= p.length(); j++) {
12
      for (int i = 1; i <= s.length(); i++) {
13
        if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.')
14
          dp[i][j] = dp[i - 1][j - 1];
15
        else if (p.charAt(j - 1) == '*')
16
          dp[i][j] =
17
              dp[i][j - 2]
18
                  || ((s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')
19
                      && dp[i - 1][j]);
20
      }
21
    }
22
    return dp[s.length()][p.length()];
23
  }
24
}