class Solution {
    public boolean isMatch(String s, String p) {
        char[] str = s.toCharArray(), pat = p.toCharArray();
        boolean[][] dp = new boolean[str.length + 1][pat.length + 1];
        dp[0][0] = true;
        // dp[i][0] = false, 0 < i
        for (int i = 1; i <= pat.length; i++)
            dp[0][i] = 1 < i && pat[i - 1] == '*' && dp[0][i - 2];
        for (int i = 1; i <= str.length; i++) {
            for (int j = 1; j <= pat.length; j++) {
                if (pat[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 2] || ((pat[j - 2] == '.' || str[i - 1] == pat[j - 2]) && dp[i - 1][j]);
                } else {
                    dp[i][j] = (pat[j - 1] == '.' || str[i - 1] == pat[j - 1]) && dp[i - 1][j - 1];
                }
            }
        }
        return dp[str.length][pat.length];
    }
}