AcWing 30. 正则表达式匹配

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 30. 正则表达式匹配原题链接困难

作者：

yxc , 2019-01-06 02:29:50 , 所有人可见 , 阅读 13333

206

82

算法

(动态规划) $O(nm)$

状态表示：f[i][j]表示p从j开始到结尾，是否能匹配s从i开始到结尾
状态转移：

如果p[j+1]不是通配符'*'，则f[i][j]是真，当且仅当s[i]可以和p[j]匹配，且f[i+1][j+1]是真；
如果p[j+1]是通配符'*'，则下面的情况只要有一种满足，f[i][j]就是真；
- f[i][j+2]是真；
- s[i]可以和p[j]匹配，且f[i+1][j]是真；

第1种情况下的状态转移很好理解，那第2种情况下的状态转移怎么理解呢？

最直观的转移方式是这样的：枚举通配符'*'可以匹配多少个p[j]，只要有一种情况可以匹配，则f[i][j]就是真；
这样做的话，我们发现，f[i][j]除了枚举0个p[j]之外，其余的枚举操作都包含在f[i+1][j]中了，所以我们只需判断
f[i+1][j]是否为真，以及s[i]是否可以和p[j]匹配即可。

时间复杂度分析： $n$ 表示s的长度， $m$ 表示p的长度，总共 $nm$ 个状态，状态转移复杂度 $O(1)$ ，所以总时间复杂度是 $O(nm)$ .

C++ 代码

class Solution {
public:
    vector<vector<int>>f;
    int n, m;
    bool isMatch(string s, string p) {
        n = s.size();
        m = p.size();
        f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
        return dp(0, 0, s, p);
    }

    bool dp(int x, int y, string &s, string &p)
    {
        if (f[x][y] != -1) return f[x][y];
        if (y == m)
            return f[x][y] = x == n;
        bool first_match = x < n && (s[x] == p[y] || p[y] == '.');
        bool ans;
        if (y + 1 < m && p[y + 1] == '*')
        {
            ans = dp(x, y + 2, s, p) || first_match && dp(x + 1, y, s, p);
        }
        else
            ans = first_match && dp(x + 1, y + 1, s, p);
        return f[x][y] = ans;
    }
};

69 评论

救赎 2022-02-28 10:10

class Solution {
public:
    string s,p;
    int m,n;
    bool dp[301][301];
    bool Match(char a ,char b){
        return a == b || a == '.' || b == '.';
    }
    bool isMatch(string _s, string _p) {
        s = _s;
        p = _p;
        m = _s.size();
        n = _p.size();

        memset(dp,0,sizeof dp);
        if(p[n-1]=='*') dp[m][n-2] = 1;
        for(int i=n-3;i>=0;i-=2){
            if(p[i] == '*') dp[m][i-1]|=dp[m][i+1] ;
        }
        dp[m][n] = 1;
        for(int j=n-1;j>=0;j--){
            for(int i=m-1;i>=0;i--){
                if(p[j+1] == '*'){
                    dp[i][j] |= dp[i][j+2];
                    if(Match(s[i],p[j])) dp[i][j]|=dp[i+1][j];
                }
                else{
                    if(Match(s[i],p[j])) dp[i][j]|=dp[i+1][j+1];
                }
            }
        }
        return dp[0][0];
    }


};

渣男 2021-08-18 12:24

生不出人，我很抱歉

明天去你那玩 2020-09-13 13:11

晕，好不容易搞清楚了递推公式，但这个dp是干啥的啊。。。还有y总的思路压根想不到啊，菜醒。。

yxc 2020-10-13 13:14

这是用记忆化搜索来实现的。也可以用循环来实现：

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        s = ' ' + s, p = ' ' + p;

        vector<vector<bool>> f(n + 1, vector<bool>(m + 1));
        f[0][0] = true;

        for (int i = 0; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
            {
                if (j + 1 < p.size() && p[j + 1] == '*') continue;

                if (i && p[j] != '*')
                {
                    f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
                }
                else if (p[j] == '*')
                {
                    f[i][j] = f[i][j - 2] || i && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
                }
            }

        return f[n][m];
    }
};

明天去你那玩 2020-10-13 19:52 回复了 yxc 的评论

感谢y总，为y总打call！！！！ORZ

求Accept 2021-12-04 15:25 回复了明天去你那玩的评论

最后一个条件判断里那么多&& || 真的很难理解啊

求Accept 2021-12-04 15:26 回复了明天去你那玩的评论

i && 的作用是什么

求Accept 2021-12-04 15:30 回复了求Accept 的评论

哦我懂了 i && 是用来限制的 i = 0时只要考虑f[i][j - 2] 针对于s = ‘’ p = ‘.*’的情况

xuyouzhi 2021-02-03 09:14

y总，这个地方，样例给的“aaa”可以和”abaca“匹配。我看着不匹配啊。可以解释下么😂，除非反着匹配，正着匹配我始终觉得不匹配

Ησυνείδησητης 10个月前

我看了很久再看了看题解终于看懂了，”*”代表的是他前面的那一个字符可以出现任意次，这样b和c都出现0次就可以理解了，匹配了

不爱编程的程序猿 2019-07-17 15:04

转态表示：f[i][j] 表示s[i,…]和p[j,…]相匹配

状态转移：
1、p[j]是正常字符，f[i][j]=s[i]==p[j]&&f[i+1][j+1];
2、p[j]是”.”，f[i][j]=f[i+1][j+1]
3、p[j+1]是”*”，s[i]==p[j]&&f[i][j]=f[i+1][j]||f[i][j+2]

注意点：
1.记忆化搜索
2.由于是从后往前进行递推判断，所以需要用到递归

yxc 2019-07-17 15:15

对滴，总结得不错！

Salix_babylonica_ 2019-09-03 19:01

赞！

cardcounter 6个月前

我个人不赞成f[i][j]用来存suffixes的匹配程度，
例如 s = “aab” p =”.*b”
p 的suffix “*b”没有意义.所以这道题目完全可以正过来写。

   def isMatch(self, s: str, p: str) -> bool:
       n, m = len(s), len(p)
       f = [[0] * (m+1) for _ in range(n+1)]
       f[0][0] = 1
       def dp(i, j):
           nonlocal f
           if f[i][j] != 0: return f[i][j]

           jj = j - 1
           ii = i - 1
           f[i][j] = -1
           if jj>=0:
               if p[jj] == '*':
                   # p[jj] repeats 0 times
                   if j >= 2 and dp(i, j - 2) == 1:
                       f[i][j] = 1


                   elif s[ii] == p[jj - 1] or p[jj - 1] == '.': # p[jj] repeats at least 1 time
                       if i >= 1 and dp(i - 1, j) == 1:
                           f[i][j] = 1
               elif p[jj] == '.':
                   if i - 1 >=0 and j - 1 >=0:
                       f[i][j] = dp(i - 1, j - 1)
               else:
                   if p[jj] == s[ii] and i - 1 >=0 and j - 1 >=0:
                       f[i][j] = dp(i - 1, j - 1)
           return f[i][j]
       return dp(n, m) == 1

慢慢_31 2024-02-23 16:54

if (f[x][y] != -1) return f[x][y];
这句代码去掉也能成功。我咋感觉不会重复调用f(x,y)呢？不是每一次都会线性增加x或者y吗？

懂王就得不懂装懂 2022-10-08 19:54

要是aaa与abbbb*aa匹配不

zzuts 2022-10-15 11:00

不匹配，* 表示他前面的字符可以出现0或n次。那么abbbb * aa ,可以看成 abbbaa,如果要匹配，要改成ab * b * b * b * aa

DataSciCoder 2021-06-16 22:04

想知道当 p[j - 1] = ‘*’，第一种情况和第二种情况应该没有交集吧？应该不会出现第一种情况满足了，然后第二种情况又满足的情况吧？

七品要员 2021-05-08 22:32

y总，想问下这段代码

        if (y == m)
            return f[x][y] = x == n;

改成
···
if(x== n) return f[x][y] = y==m;
```
为什么会报错啊，求解

hzoi 2021-07-08 20:33

s遍历完了，p结尾还可能有，比如结尾为 a*，即字母 + 星号，当星号表示 0 个时也是正确的

_M_ 2021-02-13 19:14

bool isMatch(char s, char p) {
int sn=strlen(s),pn=strlen(p),i=0,j=0,t;
while(i<sn && j<pn){
if(p[j]==’.’){
if(j+1<pn && p[j+1]==’’) return true;
else{
i;
j;
}
}
else{
if(p[j]==s[i]){
t=s[i];
i;
if(j+1<pn && p[j+1]==’*’){
while(i<sn && s[i]==s[i-1]) i;
j+=2;
while(p[j]==t) j;
}
else j;
}
else if(j+1<pn && p[j+1]==’’) j+=2;
else break;
}
}
if(sn==0){ //前者为空时
while(j<pn){
if(p[j]==’‘ || (j+1<pn && p[j+1]==’’)) j++;
else break;
}
}
if(i==sn && j==pn) return true;
else return false;
}
修改了一下萌新代码真的丑陋辛苦大佬

_M_ 2021-02-13 19:05

bool isMatch(char s, char p) {
int sn=strlen(s),pn=strlen(p),i=0,j=0;
// printf(“%d %d\n”,sn,pn);
while(i<sn && j<pn){
if(p[j]==’.’){
if(j+1<pn && p[j+1]==’’) return true;
else{ i; j;}
}
else{
if(p[j]==s[i]){
i;
if(j+1<pn && p[j+1]==’*’){
while(i<sn && s[i]==s[i-1]) i;
j+=2;
}
else j;
}
else if(j+1<pn && p[j+1]==’’) j+=2;
else break;
}
}
if(sn==0){ //前者为空时
while(j<pn){
if(p[j]==’‘ || (j+1<pn && p[j+1]==’*’)) j;
else break;
}
}
if(i==sn && j==pn) return true;
else return false;
}
代码AC了但是我觉得 ”aaab” “aab” 我写的这个会返回false 正确应该是true
刚跨考的萌新求大佬指点一下

null_7 2020-12-28 17:52

...
else if (p[j] == '*')
{
f[i][j] = f[i][j - 2] || i && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
}
...

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

这段里的这个f[i - 1][j]是什么意思呢？

GinSoda 2021-03-25 17:47

当p[j]='*',
如果dp[i][j-2]为真，说明'*'匹配了0个字符，dp[i][j]也为真
如果dp[i-1][j]为真，所以'*'可能匹配了字符，并且当p[j-1]匹配s[i]时，dp[i][j]为真

苏醒 2020-06-25 10:28

为什么要用ans暂时储存呢？在计算中不会再次访问到f[x][y]吧

yxc 2020-07-17 14:25

ans这个变量比f[x][y]短一点。

Ricardo_T_Hu 2020-03-14 19:05

请问，如果string 已经到了s[n]位置，而exp还没有到p[m]位置，这种边界情况似乎没考虑进去

yxc 2020-03-25 01:50

代码的这部分写得比较绕，这里的判断藏在first_match里了，只有当x < n的时候才会等于true，也才会执行x + 1的递归，所以处理过程中是不会越界的。

神经蛙_3 2020-03-09 12:12

楼主写的太漂亮，完美

class Solution {
public:
    vector<vector<int>>f;
    int n, m;
    bool isMatch(string s, string p) {
        n = s.size();
        m = p.size();
// 为什么不是n，m 因为考虑到s,p都为空的情况
        f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
        return dp(0, 0, s, p);
    }

    bool dp(int x, int y, string &s, string &p)
    {
//利用到的f[x][y] 有值说明已经计算过，直接返回不需要再去递归。利用到已经计算到的值，截枝不让重复递归
        if (f[x][y] != -1) return f[x][y];
        if (y == m)
            return f[x][y] = x == n;
        bool first_match = x < n && (s[x] == p[y] || p[y] == '.');
        bool ans;
        if (y + 1 < m && p[y + 1] == '*')
        {
            ans = dp(x, y + 2, s, p) || first_match && dp(x + 1, y, s, p);
        }
        else
            ans = first_match && dp(x + 1, y + 1, s, p);
        return f[x][y] = ans;
    }
};

yxc 2020-03-13 23:42

谢谢hh

神经蛙_3 2020-03-27 10:48 回复了 yxc 的评论

再补充下

 bool dp(int x, int y, string &s, string &p)
    {  
        if (f[x][y] != -1) return f[x][y];
        if (y == m)
            return f[x][y] = x == n; 
        // x<n 防止了下次进入dp后 "if (f[x][y] != -1)" 的越界; 因为下面进入dp(x+1,,,,)都用first先做了限制
        bool first_match = x < n && (s[x] == p[y] || p[y] == '.');
        bool ans;
        if (y + 1 < m && p[y + 1] == '*')
        {// y+2 在进入下一次dp，不会越界;因为进入下一次dp前提是y+1是‘*’,*位于p最后一个位时，数组f可以到最后一位加一
            ans = dp(x, y + 2, s, p) || first_match && dp(x + 1, y, s, p);
        }
        else
         // y递增加1，总会遇到的y==m后返回
            ans = first_match && dp(x + 1, y + 1, s, p);
        return f[x][y] = ans;
    }

yxc 2020-04-04 03:20 回复了神经蛙_3 的评论

很棒hh

TK 2019-10-31 01:04

yls这里的递归解法就是指dfs吗？用dfs不用动归也可以解，时间复杂度都是o(nm)吗？

yxc 2019-10-31 02:23

这里的dfs也叫记忆化搜索，保证了每个f[x][y]都只会被计算一次，所以时间复杂度是 $o(nm)$ 。纯暴力搜索不加记忆化的话，时间复杂度就是指数级别了。

TK 2019-10-31 07:44 回复了 yxc 的评论

理解了，没有意识到这是记忆化搜索的应用，谢谢yls！

Java 2019-09-29 13:14

if (y + 1 < m && p[y + 1] == ‘*’)
{
ans = dp(x, y + 2, s, p) || first_match && dp(x + 1, y, s, p);

    }
    else
        ans = first_match && dp(x + 1, y + 1, s, p);

这里的else不是也可能否定y + 1 < m这个判断条件么，为什么没报数组下标出界异常？

yxc 2019-10-02 20:00

p的下标只能到m - 1，但f的下标可以到m。

nihaotian 2019-09-12 16:54

为什么这里把

ans = first_match && dp(x + 1, y + 1, s, p);

写成

            ans =  dp(x + 1, y + 1, s, p) && first_match;

就会出现段错误

yxc 2019-09-12 20:41

调整顺序之后可能会导致数组下标越界：当 x == n的时候也会递归到下一层了，那么此时 x = n + 1，就会越界了。

散步社社长 2019-09-06 15:18

这个题怎么写非递归的？我写了半天没写出来

yxc 2019-09-06 17:17

非递归版本可以参考这份代码LeetCode 10，题目是一样的。
不过状态表示稍微调整了一下：

在这份代码里 f[i][j]表示p[1~j]，是否能匹配s[1~i]。

两种表示方式都是可以的。

App 内打开