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

Hey, great question! 你提到能用线性方法解决这个支持.和*的正则匹配问题，但好奇动态规划的思路——其实DP之所以成为这类问题的标准解法，是因为它能完美处理*带来的「匹配零个/多个前面元素」这种不确定的分支情况，避免贪心可能踩的坑。下面我一步步拆解DP的核心逻辑，结合你给出的测试用例来解释：

1. 先明确状态定义 #

我们定义一个二维布尔数组 dp[i][j]，它的含义是：字符串s的前i个字符和模式p的前j个字符是否匹配。这里的i和j都从0开始计数（0代表空字符串/空模式）。

举几个对应你测试用例的例子：

• dp[0][0] = true：空字符串和空模式肯定匹配
• dp[2][1]对应s="aa"和p="a"的匹配情况，也就是你第一个测试用例，结果是false

2. 状态转移的核心逻辑 #

这是DP解法的灵魂，我们分三种情况逐一分析：

情况1：当前模式字符是普通字符（非./*） #

如果s[i-1] == p[j-1]（注意：i/j是前i/j个字符，所以对应字符串的索引是i-1和j-1），那么dp[i][j] = dp[i-1][j-1]——意思是只要前面的子串匹配，当前字符也匹配，整体就匹配。

如果字符不相等，那dp[i][j]直接为false。

情况2：当前模式字符是. #

.可以匹配任意单个字符，所以逻辑很简单：只要前面的子串匹配，当前就匹配，即 dp[i][j] = dp[i-1][j-1]

情况3：当前模式字符是* #

这是最复杂的情况，因为*要处理「匹配零个前面元素」或「匹配一个/多个前面元素」两种场景：

• 子情况3.1：*匹配零个前面的元素
  相当于直接忽略模式里的x*（也就是p[j-2]和p[j-1]这两个字符），所以状态转移为：dp[i][j] = dp[i][j-2]
  比如你给出的测试用例isMatch("aab", "c*a*b")，当匹配到c*时，c和s的第一个字符a不匹配，我们就用「零个匹配」的逻辑，直接看s前2个字符和跳过c*后的模式是否匹配。

• 子情况3.2：*匹配一个或多个前面的元素
  这需要满足两个前提：

  1. *前面的字符（p[j-2]）等于当前s的字符（s[i-1]），或者p[j-2]是.（能匹配任意字符）
  2. 此时我们看s的前i-1个字符和当前模式是否匹配（相当于把当前s的字符算进*的匹配序列里），即 dp[i][j] = dp[i-1][j]

  把两种子情况结合起来，遇到*时的完整状态转移公式是：

  dp[i][j] = dp[i][j-2] || ( (s[i-1] == p[j-2] || p[j-2] == '.') && dp[i-1][j] )
  

  比如你的测试用例isMatch("aa", "a*")，当i=2,j=2时，p[j-2]是a等于s[i-1]的a，所以我们看dp[1][2]；而dp[1][2]又会触发「零个匹配」的逻辑，看dp[0][2]（dp[0][2]是true，因为a*可以匹配空字符串），最终dp[2][2] = true，符合测试结果。

3. 初始化的关键细节 #

• 首先dp[0][0] = true：空字符串匹配空模式，这是基础。
• 对于dp[0][j]（空字符串匹配模式的前j个字符），只有当模式是x*y*z*这种连续的「字符+*」组合时才为true。比如dp[0][2]对应p="a*"，结果是true；dp[0][4]对应p="c*a*"，结果也是true。初始化时要处理这种情况：如果p[j-1]是*，那么dp[0][j] = dp[0][j-2]。

4. 结合测试用例验证逻辑 #

拿isMatch("ab", ".*")来走一遍流程：

1. 计算dp[2][2]：p[j-1]是*，先看dp[2][0]（false），再检查p[j-2]是.，能匹配s[1]的b，所以看dp[1][2]
2. 计算dp[1][2]：同样遇到*，看dp[1][0]（false），p[j-2]是.能匹配s[0]的a，所以看dp[0][2]
3. 计算dp[0][2]：p[j-1]是*，所以dp[0][2] = dp[0][0] = true
4. 回溯回去，dp[1][2] = true，dp[2][2] = true，和测试结果一致。

再看isMatch("aab", "c*a*b")：

• 最后匹配到b时，p[j-1]是b等于s[2]的b，所以dp[3][5] = dp[2][4]
• dp[2][4]对应s前2个aa和p前4个c*a*，遇到*后，p[j-2]是a等于s[1]的a，所以看dp[1][4]
• dp[1][4]同理，看dp[0][4]，而dp[0][4] = dp[0][2] = dp[0][0] = true
• 最终回溯得到dp[3][5] = true，符合测试结果。

为什么动态规划比线性贪心更可靠？ #

贪心在某些场景下会出错，比如s="aaa"，p="a*a"：贪心会先把a*匹配所有3个a，剩下的s为空，p还有一个a，就会返回false，但实际上a*可以匹配前2个a，最后一个a匹配p的最后一个a，应该返回true。而动态规划会遍历所有可能的匹配分支，不会漏掉这种正确的匹配路径。

内容的提问来源于stack exchange，提问作者Rnet