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

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的解决方案，比如下面这个：

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问题（如2D网格最短路径和二进制2D网格中的最大正方形），在那里使用DP表对我来说非常合理。然而，在这里，我完全迷失了方向，我无法理解如何通过遍历2D表来解决此问题。此外，当字符不匹配时，我们似乎知道了，所以我不明白为什么我们不在那里停止搜索（这也可能是因为我对表格遍历如何导致解决方案缺乏理解）。有没有关于这类问题的清晰直观的解释？

- Rnet

---

@rici 谢谢，结果我误解了整个问题陈述。那么请忽略我的两条评论，非常抱歉！ - Gassa

你能解释一下为什么 isMatch("aa", "a") 返回 false 吗？我曾经使用过的任何正则表达式引擎都会在要求在字符串 "aa" 中查找正则表达式 "a" 的匹配项时成功。 - Jim Mischel

@JimMischel 这是一个简化的正则表达式问题，他们希望所有文本字符都能被模式匹配。在 "aa" 中，没有剩余的模式字符可以匹配第二个 'a'。 - Rnet

Answer 1

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

1. 问题是否可以使用递归解决？这意味着它是否可以表示为相同类型的较小子问题？

2. 在递归树中，较小的子问题是否会重复？如果是，那么可以将较小问题的结果存储在一种方式中，以便在遇到相似的子问题时可以访问结果。这通常称为记忆化。

现在让我们先了解线性方式求解时解决问题的方法。

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

- 情况1：第一个字符匹配或模式的第一个字符是'.'。 - 情况1.1：下一个字符是'*'。 - 情况1.2：下一个字符不是'*'。 - 情况2：第一个字符不匹配。 - 情况2.1：下一个字符是'*'。 - 情况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")

第一个条件的“||”部分涵盖了模式中可选字符的情况，因为它后面跟着'*'，而第二个部分涵盖了匹配字符重复的情况。

类似地，可以为所有情况形成子问题。情况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) == '*';
}

如果你仔细看，只有三行被更改为DP解决方案而不是递归解决方案。

- Abhishek Jha