使用动态编程理解正则表达式字符串匹配

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

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

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

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 的解决方案，如下所示，

class Solution {
    public boolean isMatch(String text, String pattern) {
        boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
        dp[text.length()][pattern.length()] = true;

        for (int i = text.length(); i >= 0; i--){
            for (int j = pattern.length() - 1; j >= 0; j--){
                boolean first_match = (i < text.length() && 
                                       (pattern.charAt(j) == text.charAt(i) ||
                                        pattern.charAt(j) == '.'));
                if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
                    dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
                } else {
                    dp[i][j] = first_match && dp[i+1][j+1];
                }
            }
        }
        return dp[0][0];
    }
}

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

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

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

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

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

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

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

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

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

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

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

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

对于情况 1.1 的例子是

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

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

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

类似地，可以为所有情况形成子问题。情况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 and 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 解决方案。