10. 正则表达式匹配

• 状态表示：s(i, j)

• 集合：s[1…i]和p[1…j]的是否匹配的判断

• 属性：bool值，是否存在一个有效方案

• 状态计算：

• 前言：2个字符匹配 == (p[i] == s[j] || s[j] == ‘.’)，称为matches(i, j)

• 情况1：p[j] != ‘*‘，s(i, j) = s(i - 1, j - 1) && matches(i, j)*

• 情况2：p[j] == ‘*’，s(i, j) = s(i, j - 2) || (mathces(i, j - 1) && s(i - 1, j))

  解释：将’*‘和前1个字符看作整体，当p[j]是’*’的时候，有2种情况：

  1. 匹配0个字符，那么相当于无视‘*’和它前1个字符；
  2. 匹配1个或多个字符。如果s(i - 1, j)为true，可以认为p[j - 1]已经匹配了前面的0个或多个字符。而我们是需要至少匹配一个的，所以还需要加上matches(i - 1, j)的条件

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

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2] || (matches(s, p, i, j - 1) && f[i - 1][j]);
                } else {
                    f[i][j] = matches(s, p, i, j) && f[i - 1][j - 1];
                }
            }
        }
        // p[j] != '*', s(i, j) = s(i - 1, j - 1) && (p[j] == '.' || s[i] == p[j])
        // p[j] == '*', s(i, j) = s(i, j - 2) ||
        //  ((p[j - 1] == s[i] || s[i] == '.') && s(i - 1, j))
        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);
    }
}