正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
返回一个布尔值，表示匹配是否覆盖整个输入字符串（而非部分）。

这是我现在在思考的题目，但是我没有思考出结果，我给你讲一下我现在的思路。按位来判断p能不能对上s。s用i计位，p按j。分情况讨论。首先是p既不是.也不是_时。从第一位开始看他们对应的位是不是一样的，如果不一样，返回false。一样的话i++,j++。如果j位变成了.那么就直接i++,j++。当然整个代码都要在先j再i的一个嵌套循环里。首先看j是不是.或者_，再看能不能和i位的对上。最困难的就是遇见j位是_的时候了，我的想法是，如果此时j+1已经到了终点，那么说明范式p的_是在最后一位，前面没出岔子的话那么这怎么都是对的。如果j+1不是到重点，后面还有，那么就要先找到p的j+1这个位，然后开一个新的循环，从目前的i位开始，看s从现在的i到结束有没有任何一位和这个相同，如果没有，那就返回false,如果有，那么我就得把现在的i变成让他相同的那个i继续前面的，直到两边都到最后一位都相同，或者i到最后一位时j的是.那就说明范式能匹配上，返回true我的想法是这样，但是我写不出这个循环的代码。请你评判一下，教教我怎么做

你的思路很接近正确方向了，但有两个关键点会让按位贪心很难写、也容易错：

星号不是“万能跳转”

只作用于它前面的那一个字符。

比如 a* 可以匹配空串、a、aa、aaa。

所以遇到 * 时，不是去“找后面某个字符首次出现”，而是要同时考虑两种可能：

把这一组 x* 当成匹配 0 次

如果当前字符能匹配 x，就让 x* 多吃一个字符，继续留在这个模式位置

“* 在末尾就一定对”不成立

例子：s=bbb, p=a*，末尾是 *，但不匹配。

只有当前缀也匹配时才成立。

最稳妥解法是动态规划（LeetCode 10 标准解）。

状态定义

dp[i][j]：s 前 i 个字符，是否能被 p 前 j 个字符完全匹配

答案是 dp[m][n]

转移

如果 p[j-1] 不是 *：

只有当前字符能对上，才有
dp[i][j] = dp[i-1][j-1]

如果 p[j-1] 是 *（注意它作用于 p[j-2]）：

先考虑匹配 0 次：dp[i][j] = dp[i][j-2]

若 s[i-1] 能和 p[j-2] 匹配，再考虑匹配至少 1 次：
dp[i][j] |= dp[i-1][j]

初始化

dp[0][0] = true

空串和模式匹配时，只有像 abc* 这种才能成立：
dp[0][j] = dp[0][j-2]（当 p[j-1] == *）

下面是可直接用的 C++ 代码：

你现在的思考方式已经很好了，差的就是把“遇到 * 时的多分支”系统化。DP正好把这个分支管理得很清晰。

如果你愿意，我下一步可以按你现在文件里的变量风格，带你一行一行把这个函数手写出来，并用 3 个测试样例走表格。

#include<string>
#include<vector>
using namespace std;


class Solution {
public:
    bool isMatch(string s, string p) {
        int m = (int)s.size(), n = (int)p.size();
        vector<vector<char>> dp(m + 1, vector<char>(n + 1, false));
        dp[0][0] = true;

        for (int j = 2; j <= n; ++j) {
            if (p[j - 1] == '*') dp[0][j] = dp[0][j - 2];
        }

        auto match = [&](int i, int j) -> bool {
            if (i == 0) return false;
            if (p[j - 1] == '.') return true;
            return s[i - 1] == p[j - 1];
        };

        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] != '*') {
                    if (match(i, j)) dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i][j - 2];
                    if (j >= 2 && match(i, j - 1)) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                }
            }
        }

        return dp[m][n];
    }
};

你这次的问题非常准确。我们就从 0 开始，只讲两件事：

dp 到底在记录什么
表是怎么一步一步填出来的

一、dp 的作用（最核心）
dp[i][j] 的意思是：

s 的前 i 个字符，能不能被 p 的前 j 个字符，完整匹配。

这里“前 i 个字符”是前缀，不是从中间截一段。

所以 dp 表不是在“直接比字符”，而是在记“前缀匹配是否成立”。

二、为什么要开 m+1 和 n+1
因为要把“空前缀”也放进来。

i=0 表示 s 的空前缀（空串）
j=0 表示 p 的空前缀（空模式）

这样才能表达这些基础事实：

空串 vs 空模式：true
空串 vs 普通字符：false
空串 vs a* 这种：有可能 true

三、填表时每个格子怎么来
假设你正在算 dp[i][j]，看 p 的第 j 个字符（代码里是 p[j-1]）：

如果不是 *
只可能一对一匹配当前字符。
当前位能匹配时：
dp[i][j] = dp[i-1][j-1]

含义：当前位匹配成功后，问题退化成“前一段是否匹配”。

如果是 *
这是重点。* 只作用于它前一个字符 x，也就是 x*。

x* 有两种合法用法：

用 0 次 x
直接跳过 x* 这一组：
dp[i][j] = dp[i][j-2]
用至少 1 次 x
前提：当前 s 字符能和 x 匹配。
然后“再多用一次 x”，所以：
dp[i][j] = dp[i][j] 或 dp[i-1][j]

这里用“或”是因为两条路任意一条通就成立。

四、你总晕的“匹配过程”其实就是“填表过程”
顺序通常是：

先填 dp[0][0] = true
初始化第 0 行（空串那一行）
再从上到下、从左到右填其他格子

每填一个格子，只看它依赖的已知格子（左上、左两格、上格）。

五、用最小例子走一遍：s=aa，p=a*
表大小是 3x3（i:0..2, j:0..2）

列含义：

j=0 空模式
j=1 a
j=2 a*

行含义：

i=0 空串
i=1 a
i=2 aa

结果表：

	空模式	a	a*
空串	T	F	T
a	F	T	T
aa	F	F	T

最后看右下角 dp[2][2]=T，所以匹配成功。

六、你现在可以这样理解一句话
dp 是“前缀是否可达”的地图。
填表就是在问：这个格子能不能从之前某个合法格子走过来。

如果你愿意，我下一步只做一件事：把你当前代码中的每一行转移都对应到这套语义，做一份“行对行翻译”，你照着就能自己写出来。

. 代表任意单个字符
.* 才是任意字符重复任意次

所以：

a* 很专一，只认 a
.* 才“万能”

快速对照：

a* 匹配 "aaaa"：可以
a* 匹配 "aaab"：不可以（最后 b 没人匹配）
.* 匹配 "aaab"：可以

#算法 #Leetcode

copyright_text

本文链接：https://afogsheep-github-io.pages.dev2025/02/28/Leetcode_正则表达式匹配/