剑指 Offer 19. 正则表达式匹配（Java动态规划）

public class Solution {
    public boolean isMatch(String s, String p) {
        //创建一个dp[][]二维数组，dp[i][j]表示s的前i个字符是否和p的前j个字符相匹配
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        //初始化dp数组,当两个字符串为空时，它们是相互匹配的，所以dp[0][0] = true
        //dp[i][0]=false，因为模式串p为空时，无法匹配字符串s
        //dp[0][j]=?，当字符串为空时，需要看情况，比如模式串为c*是可以和空串相匹配的
        dp[0][0] = true;
        for (int i = 0; i <= s.length(); i ++) {
            for (int j = 1; j <= p.length(); j ++) {
                // 如果模式串的前一个字符为*
                if (p.charAt(j - 1) == '*') {
                    // 跳过*组合的匹配, 比如a与b*a匹配时可以选择不匹配b字符
                    dp[i][j] = dp[i][j - 2];
                    // 跳过*组合的匹配或*组合匹配字符串的一个字符并将这个字符丢掉
                    if (matchChar(s, p, i, j - 1)) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                } else {
                    // 都匹配一个字符, 比如ab与ab， dp[2][2] = d[1][1] = dp[0][0] =true
                    if (matchChar(s, p, i, j)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
        }
        return dp[s.length()][p.length()];
    }

    /**
     *
     * @param s 字符串
     * @param p 模式串
     * @param i 字符串的第i个字符位置
     * @param j 模式串的第j个字符位置
     * @return 字符串的第i - 1个字符和模式串的第j - 1个字符是否相等
     */
    private boolean matchChar(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);
    }
}