使用动态规划了解正则表达式字符串匹配

Question

我遇到了这个问题，它要求您实现一个支持 '.' 的正则表达式匹配器。和“*”，其中

'.' 匹配任何单个字符。

'*' 匹配零个或多个前面的元素。

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

虽然我能够以线性方式解决这个问题，但我遇到了很多使用 DP 的解决方案，如下所示，

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

我很难理解这一点。我已经解决了一些涉及网格的 DP 问题（2d 网格中的最短路径，二进制 2d 网格中的最大正方形），使用 DP 表对我来说非常有意义。但是在这里我完全迷失了，我无法理解遍历二维表如何帮助解决这个问题。此外，我们似乎知道循环中的字符何时不匹配，所以我不明白为什么我们不在那里终止搜索（这也可能是由于我对表遍历如何导致一个办法）。对于此类问题，是否有清晰直观的解释？

Answer 1

使用 DP 解决此类问题的直觉是找出以下问题的答案

1. 问题可以用递归来解决吗？这意味着它可以用同类型的较小子问题来表示？
2. 较小的子问题是否会在递归树中重复？如果是，可以将较小问题的结果存储为每当遇到类似的子问题时都可以在 O(1) 中访问结果的方式。这通常称为记忆化。

让我们首先了解您在以线性方式求解时可能找到的问题的解决方案。

1. 将文本与模式匹配时，第一个字符要么匹配，要么不匹配。

   情况 1：第一个字符匹配或模式的第一个字符是“.”

   案例 1.1 下一个字符是“*”

   情况 1.2 下一个字符不是 '*'

   情况 2：第一个字符不匹配

   案例 2.1 下一个字符是 '*'

   case 2.2 下一个字符不是 '*'

现在让我们找出前面讨论的解决上述问题的两个步骤。

对于情况 1.1 的例子是

isMatch("a", "a*a")这 isMatch("aab", "a*b") 相当于解决

isMatch("a", "a") || isMatch("", "a*a")和

isMatch("aab", "b") || isMatch("ab", "a*b")分别。条件的第一部分||涵盖了模式中可选字符的场景，因为它后面跟着“*”，第二部分涵盖了匹配字符重复的场景。

类似地，可以为所有情况形成子问题。case 2.2 应该直接返回 false。

下面是使用递归方法的java代码

public boolean isMatch(String text, String pattern) {
    dp = new Boolean[text.length()][pattern.length()];
    return isMatch(text, pattern, 0, 0);
}

private boolean isMatch(String text, String pattern, int ti, int pi) {

    if (pi == pattern.length() && ti < text.length()) return false;

    if (ti == text.length() && pi == pattern.length()) return true;

    if (ti == text.length()) {
        return isNextCharStar(pattern, pi) && isMatch(text, pattern, ti, pi + 2);
    }


    boolean result;
    final boolean hasFirstMatched = text.charAt(ti) == pattern.charAt(pi) || pattern.charAt(pi) == '.';

    if (isNextCharStar(pattern, pi)) {
        result = isMatch(text, pattern, ti, pi + 2);
        if (hasFirstMatched) {
            result = result || isMatch(text, pattern, ti + 1, pi);
        }
        return result;
    }

    return hasFirstMatched && isMatch(text, pattern, ti + 1, pi + 1);

}

private boolean isNextCharStar(String pattern, int pi) {
    return pi < pattern.length() - 1 && pattern.charAt(pi + 1) == '*';
}

现在让我们应用记忆步骤。如果我们在返回之前开始保存结果，我们就可以在下次重用它。我们应该如何以及在哪里保存它？对于ti和的所有可能组合，pi我们必须存储结果。其中ti是文本索引，pi是模式索引。所以大小的二维数组text.length * pattern.length应该足够了。以下是上述更改后的代码

Boolean [][] dp;

public boolean isMatch(String text, String pattern) {
    dp = new Boolean[text.length()][pattern.length()];
    return isMatch(text, pattern, 0, 0);
}

private boolean isMatch(String text, String pattern, int ti, int pi) {

    if (pi == pattern.length() ) return ti == text.length();

    if (ti == text.length()) {
        return isNextCharStar(pattern, pi) && isMatch(text, pattern, ti, pi + 2);
    }

    if(dp[ti][pi] != null) return dp[ti][pi];

    boolean result;
    final boolean hasFirstMatched = text.charAt(ti) == pattern.charAt(pi) || pattern.charAt(pi) == '.';

    if (isNextCharStar(pattern, pi)) {
        result = isMatch(text, pattern, ti, pi + 2);
        if (hasFirstMatched) {
            result = result || isMatch(text, pattern, ti + 1, pi);
        }
        dp[ti][pi] = result;
        return result;
    }

    dp[ti][pi] = hasFirstMatched && isMatch(text, pattern, ti + 1, pi + 1);
    return dp[ti][pi];

}

private boolean isNextCharStar(String pattern, int pi) {
    return pi < pattern.length() - 1 && pattern.charAt(pi + 1) == '*';
}

如果您仔细观察，只更改了 3 行，使其从递归解决方案变为 DP 解决方案。