[数据结构与算法]Leetcode 10-正则表达式匹配

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        //f[0][0]对应两个字符串都为空的情况
        boolean[][] f = new boolean[m + 1][n + 1];

        f[0][0] = true;
        //为什么j从1到n???????????
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                //p[j-1]是'*'需要特殊判断
                if (p.charAt(j - 1) == '*') {
                    //1.抛弃'p[j]*'这个选项，s[i]和p[j-2]匹配则为true
                    f[i][j] = f[i][j - 2];
                    //2.考虑'p[j]*'这个选项，s[i]和p[j-1]匹配则为true
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                }else{
                    //不是'*'，不需要特殊判断
                    //s[i]和p[j]匹配
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }
    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }

}