劍指 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);
    }
}