10. 正则表达式匹配：NFA 非确定有限状态自动机 或 动态规划.md

题目简述：

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

• '.' 匹配任意单个字符
• '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。

提示：

• s 只包含从 a-z 的小写字母。
• p 只包含从 a-z 的小写字母，以及字符 . 和 *。
• 保证每次出现字符 * 时，前面都匹配到有效的字符

题目链接：10. 正则表达式匹配

关键

无论是考虑 NFA 还是动态规划，关键是将 "x*" 视为一个整体，而不是单独处理 '*'。

因为 "x*" 可能可以被视为 ""，即匹配 0 个字符的情况。

动态规划

思路

设 $dp[i][j]$ 表示 p[0] 至 p[j] 的子模式能否匹配 s[0] 至 s[i] 的子串，则

• 若 p[j] 为 '.'，则 $dp[i][j]=dp[i-1][j-1]$

• 若 p[j] 为普通字符，如果 p[j] 匹配 s[i] 则 $dp[i][j]=dp[i-1][j-1]$，反之则子模式不匹配子串，$dp[i][j]=\mathrm{false}$

• 若 p[j] 为 '*'，

  • p[j] 可能匹配 0 个字符，此时 $dp[i][j]=dp[i][j-2]$
  • p[j] 可能匹配 1 个字符或多个字符，
    • 若 p[j-1] 为普通字符且不能匹配 s[i]，此时 $dp[i][j]=\mathrm{false}$
    • 否则，意味着要么 p[j-1] 为 '.'，要么 p[j-1] 为普通字符且能够匹配 s[i]，此时 $dp[i][j]=dp[i-1][j]$（此处体现最优子结构）

  综上，$dp[i][j]=dp[i][j-2]\lor\Big(dp[i-1][j]\land\big(p[j-1]=s[i]\lor p[j-1]=,'.'\big)\Big)$

为避免特殊处理边界情况，设 $dp[0][0]=\mathrm{true}$ 表示空模式能够匹配空串。相应地进行初始化： $$ \forall i>0,\ \ dp[i][0]=\mathrm{false} $$

$$ \forall j>0,\ \ dp[0][j]=\left{\begin{align}&\mathrm{false},&&p[j-1]\neq\ '\ast'\\&dp[0][j-2],&&p[j-1]=\ '\ast'\end{align}\right. $$

在新定义下 $dp[i][j]$ 是 1-based 的。

最终 $dp$ 矩阵的右下角元素即为问题的解。

算法实现

算法的时间复杂度与空间复杂度均为 $O(mn)$。

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];

        // init
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) dp[0][j] = p.charAt(j - 1) == '*' ? dp[0][j - 2] : false;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {

                switch (p.charAt(j - 1)) {
                    case '.':
                        dp[i][j] = dp[i - 1][j - 1];
                        break;
                    case '*':
                        dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (p.charAt(j - 2) == s.charAt(i - 1) || p.charAt(j - 2) == '.'));
                        break;
                    default:
                        dp[i][j] = s.charAt(i - 1) == p.charAt(j - 1) ? dp[i - 1][j - 1] : false;
                        break;
                }
            }
        }
        
        return dp[m][n];
    }
}

算法的改进实现

算法的时间复杂度仍为 $O(mn)$，使用滚动数组优化空间开销，空间复杂度为 $O\big(\min{m,n}\big)$（虽然下面的实现是 $O(n)$ 的，懒得分情况讨论了）。

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[] dp1 = new boolean[n + 1];
        boolean[] dp2 = new boolean[n + 1];

        // init
        dp1[0] = true;
        for (int j = 1; j <= n; j++) dp1[j] = p.charAt(j - 1) == '*' ? dp1[j - 2] : false;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {

                switch (p.charAt(j - 1)) {
                    case '.':
                        dp2[j] = dp1[j - 1];
                        break;
                    case '*':
                        dp2[j] = dp2[j - 2] || (dp1[j] && (p.charAt(j - 2) == s.charAt(i - 1) || p.charAt(j - 2) == '.'));
                        break;
                    default:
                        dp2[j] = s.charAt(i - 1) == p.charAt(j - 1) ? dp1[j - 1] : false;
                        break;
                }
            }

            boolean[] tmp = dp1;
            dp1 = dp2;
            dp2 = tmp;
            dp2[0] = false;
        }

        return dp1[n];
    }
}

NFA 非确定有限状态自动机

思路

或许可以改为 DFA 实现，但可能太麻烦了。

如果考虑 NFA，那么实际上就是动态规划方法的记忆化搜索版本，原理与动态规划是相同的。

代码

class Solution {

    private String s, p;
    private int m, n;
    // memo[i][j]：从 (i, j) 出发能否接受；null=未知，true/false=已算
    private Boolean[][] memo;

    public boolean isMatch(String s, String p) {
        this.s = s; this.p = p;
        this.m = s.length(); this.n = p.length();
        this.memo = new Boolean[m + 1][n + 1];
        return dfs(0, 0);
    }

    private boolean dfs(int i, int j) {
        // 记忆化
        if (memo[i][j] != null) return memo[i][j];

        boolean ans;

        // 终止：模式走完则文本也必须走完
        if (j == n) {
            ans = (i == m);
        } else {
            // 当前是否首字符可匹配（仅当 i<m 才能消费字符）
            boolean firstMatch = (i < m) &&
                    (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');

            // 看下一位是否为 '*'，把 "x*" 视为一个原子（NFA 的关键）
            if (j + 1 < n && p.charAt(j + 1) == '*') {
                // 两种 NFA 转移：
                // 1) ε-跳转：跳过 "x*"（0 次）
                // 2) 消费一字符并留在 j（≥1 次），前提是首字符可匹配
                ans = dfs(i, j + 2) || (firstMatch && dfs(i + 1, j));
            } else {
                // 普通转移：必须首字符匹配，然后 i、j 同步前进
                ans = firstMatch && dfs(i + 1, j + 1);
            }
        }

        return memo[i][j] = ans;
    }
}