Leetcode10-正则表达式匹配

发布于:2025-03-13 ⋅ 阅读:(27) ⋅ 点赞:(0)

题目链接:10. 正则表达式匹配 - 力扣(LeetCode)

这题是真的难,读懂题意就很难

首先要搞懂 *匹配零个或多个前面的那一个元素”这句话的含义

  • 第一次阅读理解可能是这样的:例如a*,匹配零个就是a,匹配一个就是aa,匹配多个就是aaaa.....
  • 然而真正的含义是:匹配0次a*变为空,匹配一次变为a,匹配多次是aaaa....

 接下来说解题思路,也是看了题解才知道用动态规划

  1. 定义dp[m+1][n+1]的状态数组,讲dp[0][0]初始化为true,表示空对空,能匹配上
  2. 有一种特殊边界情况处理,就是当s为空(即dp[0][j])的时候,并不是一定匹配不上。比方说,此时p为a*a*a*,将*匹配0次,就能匹配上
  3. 遍历字符串,做状态转移:分两种情况

第一种情况:当s[i-1][j-1]==p[i-1][j-1]或者p[j-1] == '.'时,dp[i][j] = dp[i-1][j-1];

if (s[i-1] == p[j-1] || p[j-1] == '.') {
    dp[i][j] = dp[i-1][j-1];
}

第二种情况,当p[j-1] == ’*时‘,又分为两种情况

情况2.1:s[i-1] == p[j-2] || p[j-2] == '.' 时,可以匹配*前面的字符一次或多次,此时的状态转移为:dp[i][j] = dp[i-1][j];

情况2.2:上面的条件不成立,则匹配0次,此时的状态转移为:dp[i][j] = dp[i][j-2];

特别说明,应该将这两种情况结合起来,而不是对立起来。下面的代码就只能通过307 / 354,s="aaa",p="ab*a*c*a"就通不过。因为就算情况1成立了,dp[i-1][j]也可能为false,而dp[i][j-2]为true。在这里踩了一坑。

for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i-1] == p[j-1] || p[j-1] == '.') {
                dp[i][j] = dp[i-1][j-1];
            } else if (p[j-1] == '*') {
                if (s[i-1] == p[j-2] || p[j-2] == '.') {
                    dp[i][j] = dp[i-1][j];//匹配一个或多个
                }else{
                    dp[i][j] = dp[i][j-2];//匹配0个               
                }
            }
        }
    }

最后的代码:

/*注意:dp[i][j] = dp[i-1][j]表示匹配一个或多个*/
bool isMatch(char* s, char* p) {
    int m = strlen(s);
    int n = strlen(p);
    
    bool dp[m+1][n+1];
    memset(dp, false, sizeof(dp));
    dp[0][0] = true;

    //比如说s为空,p为a*a*a*,能匹配成功。所以不能直接将dp[0][j]置为false
    for(int j = 1; j <=n; j++) {
        if (p[j-1] == '*') {
            dp[0][j] = dp[0][j-2];
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i-1] == p[j-1] || p[j-1] == '.') {
                dp[i][j] = dp[i-1][j-1];
            } else if (p[j-1] == '*') {
                if (j > 1) {
                    dp[i][j] = dp[i][j-2];//匹配0个 
                    if (s[i-1] == p[j-2] || p[j-2] == '.') {
                        dp[i][j] = dp[i][j] || dp[i-1][j];//匹配一个或多个
                    }
                }
            }
        }
    }
    return dp[m][n];
}

还可以用递归的方法,理解起来感觉简单一些


bool isMatch(char* s, char* p) {
    if(strlen(s) == 0){
        if (strlen(p) == 0){
            return true;
        }
        if (p[1] == '*') {
            return isMatch(s, &p[2]);
        }
        return false;
    }
    bool first_match = (s != NULL && (s[0] == p[0] || p[0] == '.'));
    
    if(strlen(p) >= 2 && p[1] == '*') {
        return isMatch(s, &p[2]) || (first_match && isMatch(&s[1], p));
    }else{
        return first_match && isMatch(&s[1], &p[1]);
    }
}