正则匹配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

这里假设字符串不包含特殊字符‘。'和‘* '，因为否则所提供的代码将无法工作!！

dp[i][j] 代表什么？

它表示，如果只考虑字符串的第一个i字符和模式的j字符，它们是否匹配？

在模式中遇到“*”时的状态转换：

案例1:在模式中‘* '之前只接受0个字符。

‘* '本身并不意味着什么。它取决于其先前的性质。

dp[i][j-2]将完全忽略模式中的前一个字符，因为它只考虑了第一个j-2字符，因此忽略了模式中的前一个字符以及‘* ' (jth character)。

如果字符串中的第一个字符和‘*’之前的字符恰好相同，或者模式中“*”之前的字符是‘’。‘然后再加一个案例。。

观察：.*可以匹配任何字符串

如果满足上述条件，那么考虑下面的情况.

Case 2:继续使用‘* '之前的字符一次或多次。

dp[i-1][j]表示这一点。记住，字符在模式中是‘* '。

因此，如果字符串的第一个i-1字符与第一j字符匹配，其中jth字符是‘* ' (这意味着我们至少在’*‘<代码>E 256>之前使用了字符)，那么我们可以说第一个<>E 157>i<代码>E 258字符串中的字符与第一个<代码>E 159jjj 260字符匹配，因为我们已经确保E 161与E 262之前的字符在模式中匹配>。

案例dp[i][j-1]是多余的，在案例2中涵盖。

dp[i][j-1]的注释：冗余的解释

dp[i][j-1]只匹配‘* '之前的字符一次。它已经在dp[i-1][j]中涵盖了。

原因：

我们知道ith字符与j-1字符匹配(请记住，我们在考虑这种情况之前检查过)。

因此，dp[i][j-1] = dp[i-1][j-2]是dp[i-1][j]计算中已经考虑的问题。

dp[i-1][j]更强大，因为dp[i-1][j] = dp[i-1][j-2] || dp[i-2][j]作为jth字符是‘* '。这就是内存属性，它允许我们使用一个字符不止一次。

Answer 2

我会用一些非正式的符号，所以请容忍我。大写将表示字符串(在模式中可以包括特殊字符)和小写字母‘。“*”代表着他们自己。

假设我们将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语句。

现在让我们以星号为例。只有忽略y* (取0 y's)，即通过将Ax与B匹配，才能将Ax与By*进行匹配。

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

但是，如果y被点或x替换，就有选择。我们将以Ax和Bx*为例。这两个选项是匹配Ax到B(表示取0 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]的，因为这会让我感到困惑。

我可能错了，但这个似乎没有必要。

它的意思是删除星号，即将“0或更多”改为“确切地一”，这已被其他两种情况所涵盖，第二种情况之后是第一种情况。