【动态规划专题】剑指 Offer 19. 正则表达式匹配-跟着帅地玩副业，开拓第二曲线PlayOffer

宁永久会员 2023年3月19日下午11:14

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for(int j = 2; j <= n; j++){
            dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';
        }
        //主要考虑星号的匹配方式
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <=n; j++){
                if(p.charAt(j - 1) == '*'){
                    dp[i][j] = dp[i][j - 2] || dp[i - 1][j] && s.charAt(i - 1) == p.charAt(j - 2) || dp[i - 1][j] && p.charAt(j - 2) == '.';
                }else{
                    if(dp[i - 1][j - 1] == true)
                        dp[i][j] = p.charAt(j - 1) == '.' || s.charAt(i - 1) == p.charAt(j - 1);
                }
            }
        }
        return dp[m][n];
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月20日上午10:31

m = len(s)
    n = len(p)
    # dp[i][j]表示s长度为i，p长度为j时，s与p是否匹配,因为是从长度为0开始的，所以这里dp的长度为【m+1】【n+1】
    dp = [[False for _ in range(n+1)] for __ in range(m+1)]

    # 初始化
    dp[0][0] = True


    # 注意两个地方，
    # 1、dp中的索引是指长度，所以在对应到字符串中的时候都要减一，
    # 2、for循环遍历的是dp中的索引，所以右边界要加1
    for _ in range(2,n+1):
        if p[_-1] == '*':
            dp[0][_] =dp[0][_-2]



    for i in range(1,m+1):
        for j in range(1,n+1):
            if p[j-1] != "*":
                if s[i-1] == p[j-1] or p[j-1] == ".":
                    dp[i][j] = dp[i-1][j-1]

            else:
                # 如果和*前一个值不相等（而且不是"."）最好的情况就是让*=0——不对前面的时进行重复,那就是和*往前两个的值进行比较
                if p[j-2] != s[i-1] and p[j-2] != ".":
                    dp[i][j] = dp[i][j-2]

                else:
                    #匹配0个or匹配1个or匹配多个
                    dp[i][j] = dp[i][j-2] or dp[i][j-1] or dp[i-1][j]

    return dp[-1][-1]

0 赞同 0 条回复

lucca 普通 2023年1月18日下午3:57

真的难

时间复杂度 O(NM)
空间复杂度 O(NM)

class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length(), m = p.length();
        boolean[][] f = new boolean[n + 1][m + 1];
        f[0][0] = true;
        for (int j = 2; j <= m; j++) {
            if (p.charAt(j-1) == '*') f[0][j] = f[0][j-2];
        }
        for (int i = 1; i <= n; i++) {
            char si = s.charAt(i-1);
            for (int j = 1; j <= m; j++) {
                char pj = p.charAt(j-1);
                if (pj != '*') {    // 不为*, 一个一个判断即可
                    if (si == pj || pj == '.') f[i][j] = f[i-1][j-1];
                } else {    // 为*, 涉及到p前一个字母的判断
                    // 没有前一个字母, *无意义 
                    if (j < 2) continue;
                    char pj2 = p.charAt(j - 2);
                    // 如果和p前一个字母匹配, 则去看s的前一个字母是否也匹配, 如果不匹配, 则看舍弃*是否匹配
                    if (si == pj2 || pj2 == '.') f[i][j] = f[i-1][j] || f[i][j-2];
                    // 如果不匹配, 舍弃*
                    else f[i][j] = f[i][j-2];
                }
            }
        }
        return f[n][m];
    }
}

0 赞同 0 条回复

派大星普通 2022年12月2日下午11:03

class Solution {
//时间复杂度O(N)
    public boolean isMatch(String s, String p) {
        if(s == null || p == null){
            return true;
        }
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for(int i = 2;i <= n;i++){
            if(p.charAt(i-1) == '*'){
                dp[0][i] = dp[0][i - 2];
            }
        }
        for(int i = 1;i <= m;i++){
            for(int j = 1; j <= n;j++){
                char pc = p.charAt(j - 1);
                char sc = s.charAt(i - 1);
                if(pc != '*'){
                    if(pc == '.' || pc == sc){
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }else {
                    if(p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.'){
                        dp[i][j] = dp[i][j - 2];
                    } else {
                        dp[i][j] = dp[i][j-2] || dp[i][j-1] || dp[i-1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
}

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月28日下午7:53

时间空间复杂度为O（nm）

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        //赋值初始值
        for(int j = 2;j <= n;j++){
            if(p.charAt(j - 1) == '*'){
                dp[0][j] = dp[0][j-2];
            }
        }
        for(int i = 1; i <= m;i++){
            for(int j = 1;j <= n;j++){
                if(p.charAt(j-1) != '*'){
                  if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.'){
                    dp[i][j] = dp[i-1][j-1];
                }
                }else{
                    if(p.charAt(j-2) != s.charAt(i-1) && p.charAt(j-2) != '.'){
                        dp[i][j] = dp[i][j-2];
                    }else{
                        dp[i][j] = dp[i-1][j-1] || dp[i][j-2] || dp[i-1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
}

0 赞同 0 条回复

Mooby 普通 2022年11月25日下午8:41

class Solution {
    public boolean isMatch(String s, String p) {
        if(s == null || p == null){
            return true;
        }
        int n = s.length();
        int m = p.length();
        boolean[][] dp = new boolean[n+1][m+1];
        dp[0][0] = true;
        for(int j = 2; j <= m; j++) {
            if(p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(p.charAt(j - 1) != '*') {
                    if(p.charAt(j-1) == '.' || p.charAt(j-1) == s.charAt(i - 1)) {
                        dp[i][j] = dp[i-1][j-1];
                    }
                } else {
                    if(p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j-2) != '.') {
                        dp[i][j] = dp[i][j-2];
                    } else {
                        dp[i][j] = dp[i][j-2] || dp[i][j-1] || dp[i-1][j];
                    }
                }
            }
        }
        return dp[n][m];
    }
}

时间：O(mn)，空间：O(mn)

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月25日上午9:26

/**
dp[i][j]表示字符串s长度为i,p长度为j时，sp是否匹配
2。比较
当p[j] 是普通字符
    相等 dp[i][j] = dp[i-1][j-1]
    不相等 dp[i][j] = false
当p[j] == .
    等价于相等的情况dp[i][j] = dp[i-1][j-1]
当p[j]== * 考虑j - 1的字符
    p[j-1]!=s[i]时候，*表示0个前面的字符 dp[i][j] = dp[i][j-2]
    p[j-1]=s[i]时候
        > *匹配0个时，dp[i][j]=dp[i][j-2]  
        > *匹配一个时，dp[i][j]=dp[i][j-1]
        > *匹配多个时，dp[i][j]=dp[i-1][j]
        等于这三个相或
初始值：
dp[0][0]=true
当p[j]=*(j >= 2) dp[0][j]=dp[0][j-2]
else false
 */
class Solution {
    public boolean isMatch(String s, String p) {
        if(s == null || p == null){
            return true;
        }
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for(int i = 2;i <= n;i++){
            if(p.charAt(i-1) == '*'){
                dp[0][i] = dp[0][i - 2];
            }
        }
        for(int i = 1;i <= m;i++){
            for(int j = 1; j <= n;j++){
                char pc = p.charAt(j - 1);
                char sc = s.charAt(i - 1);
                //当pc != *
                if(pc != '*'){
                    if(pc == '.' || pc == sc){
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }else {
                    //第j - 1个字符不匹配
                    if(p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.'){
                        dp[i][j] = dp[i][j - 2];
                    } else {
                        //分别表示，匹配0个 匹配1个 匹配多个
                        dp[i][j] = dp[i][j-2] || dp[i][j-1] || dp[i-1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
}

0 赞同 0 条回复

【动态规划专题】剑指 Offer 19. 正则表达式匹配

共以下 7 个回答

真的难

# 回答此问题取消回复

【动态规划专题】剑指 Offer 19. 正则表达式匹配

共以下 7 个回答

真的难

# 回答此问题 取消回复

# 回答此问题取消回复