public class 正则表达式匹配 {
    public boolean isMatch(String s, String p) {
        int n = s.length(), m = p.length();
        s = " " + s;p = " " + p;
        boolean[][] f = new boolean[n+1][m+1];
        f[0][0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                //首先判断一下模式串的下一个待匹配字符是不是“*”，如果是，则跳过当前模式串字符的匹配（因为在这里是把 “x*”看作一个字符进行匹配）
                if (j+1 < p.length() && p.charAt(j+1) == '*') continue;//当模式串还有未匹配的字符且下一位是“*”时，模式串后移一位。

                if (i != 0 && p.charAt(j) != '*'){
                    //当p[j]不为“*”时，要么s[i] == p[j],要么p[j] == "."
                    f[i][j] = f[i-1][j-1] && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
                }else if (p.charAt(j) == '*'){
                    /**
                     *  在这里 f[i][j]   = f[i][j-2] || f[i-1][j-2]&&s[i]==p[j-1] || f[i-2][j-2]&&s[i-1]==p[j-1]&&s[i]==p[j-1] || ......
                     *       f[i-1][j]  =              f[i-1][j-2]               || f[i-2][j-2]&&s[i-1]==p[j-1]               || ......
                     *  可以找到规律，即：f[i][j] = f[i][j-2] || (f[i-1][j] && s[i] == p[j-1])
                     *  而由于使用了 i-1 ，故需要判断一下 i 是否不为 0
                     */
                    f[i][j] =f[i][j-2] || ( i != 0 && f[i-1][j] && (s.charAt(i) == p.charAt(j-1) || p.charAt(j-1) == '.') );
                }
            }
        }
        return f[n][m];
    }
}