正则表达式匹配 dp

Question

我试图理解一种著名的正则表达式匹配 DP 算法。以防万一，人们不知道这是描述和算法。

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

---

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true


static boolean isMatch(String s, String p) {
    boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
    dp[0][0] = true;
    for (int i = 1; i < dp[0].length; i++) {
        if (p.charAt(i - 1) == '*') {
            dp[0][i] = dp[0][i - 2];
        }
    }
    for (int i = 1; i < dp.length; i++) {
        for (int j = 1; j < dp[0].length; j++) {
            char schar = s.charAt(i - 1);
            char pchar = p.charAt(j - 1);
            if (schar == pchar || pchar == '.') {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (pchar == '*') {
                if (schar != p.charAt(j - 2) && p.charAt(j - 2) != '.') {
                    //   - a b *
                    // - t f f f
                    // a f t f t // b != a and b != '.' thus treat b* as 0 match
                    dp[i][j] = dp[i][j - 2];
                } else {
                    //   - a b *
                    // - t f f f
                    // a f t f t
                    // b f f t t // dp[i][j - 2] 0 match or dp[i][j - 1] 1 math or dp[i - 1][j] 2+ match (not sure why)
                    dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];
                }
            }
        }
    }
    return dp[s.length()][p.length()];
}

大部分我都听懂了，但是这部分我没听懂

dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];

dp[i - 1][j] 人们说这将涵盖 2+ 场比赛，但不理解这部分。有人可以解释为什么我需要检查 dp[i - 1][j] 吗？

Answer 1

我将使用更非正式的符号，请耐心等待。大写字母将表示字符串(在模式中可能包含特殊字符)和小写字母“.”而“*”将代表他们自己。

假设我们正在将 Ax 与 Bx 进行匹配，这是一些以 A 开头的字符串(它本身就是一个字符串，如 xyzz)以 'x' 结尾，具有以 B 开头的模式(它本身就是一个模式，因为例如，x.*) 以“x”结尾。结果与将 A 匹配到 B 的结果相同(因为我们别无选择，只能将 x 匹配到 x)。

我们可以这样写:

isMatch(Ax, Bx) = isMatch(A, B)

同样，将 Ax 与 By 匹配是不可能的。

isMatch(Ax, Bx) = false

很简单。所以这将对应于两个嵌套循环中的第一个 if 语句。

现在让我们以星号为例。将 Ax 匹配到 By* 只能通过忽略 y*(y 取零)来完成，即通过将 Ax 匹配到 B。

isMatch(Ax, By*) = isMatch(Ax, B)

但是，如果 y 被点或 x 代替，则有选择。我们将以 Ax 和 Bx* 为例。这两个选项是将 Ax 匹配到 B(意味着取零个 x)或将 A 匹配到 Bx*(意味着取一个 x，但我们仍然可以取更多，这样模式就不会改变):

isMatch(Ax, Bx*) = isMatch(Ax, B) || isMatch(A, Bx*)

在您的代码中，最后一个将转换为:

dp[i][j] = dp[i][j - 2] || dp[i - 1][j]

现在我想知道你的问题是否真的是关于 dp[i][j - 1] 的，因为那会让我感到困惑。

我可能是错的，但那个似乎是不必要的。

意思是去掉星号，即变“零个或多个”到“恰好一个”，这已经被其他两个案例所涵盖，先是第二个，然后是第一个。