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

招舟子普通 2023年12月10日下午5:53

class Solution {
public boolean articleMatch(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 i=2;i<n+1;i++){
if(p.charAt(i-1)‘‘){
dp[0][i] = dp[0][i-2];
}
}
for(int i=1;i<m+1;i++){
for(int j=1;j<n+1;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[m][n];

}
动态规划时间复杂度:O(mn)
空间复杂度:O(mn)

0 赞同 0 条回复

张开怀普通 2023年7月24日下午3:53

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.length();
        int m = p.length();
        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
        dp[0][0] = true;
        for (int j = 2; j <= m; j++) {
            if (p[j - 1] == '*' && dp[0][j - 2]) {
                dp[0][j] = true;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; 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] || dp[i][j - 2];
                    } else {
                        dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }
        return dp[n][m];
    }
};

时间复杂度:O(mn)
空间复杂度:O(mn)

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月24日上午12:56

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if s is None or p is None:
            return True

        n = len(s)
        m = len(p)
        dp = [[False] * (m + 1) for _ in range(n + 1)]

        dp[0][0] = True

        for j in range(2, m + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]

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

        return dp[n][m]

好难。。。

0 赞同 0 条回复

BOZ 普通 2023年7月22日下午12:13

【思路】DP，dp[i][j]代表s[:i]与p[:j]能否被匹配上
【复杂度】时间O(mn)，空间O(mn)

class Solution {
public:
    bool isMatch(string s, string p) {
        // empty string check
        if (s.empty() && p.empty()) return true;
        if (p.empty()) return false;

        // initialize dp array
        int m = s.length(), n = p.length();
        bool **dp = new bool*[m + 1];
        for (int i = 0; i < m + 1; i++) dp[i] = new bool[n + 1];

        // fill the first line and first row
        dp[0][0] = true; dp[0][1] = false;
        for (int i = 1; i < m + 1; i++) dp[i][0] = false;
        for (int j = 2; j < n + 1; j++) {
            if (p[j - 1] == '*') dp[0][j] = dp[0][j - 2];
            else dp[0][j] = false;
        }

        // dp algorithm
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                char s_i = s[i - 1], p_j = p[j - 1];
                if (p_j == '*') {
                    if (j < 2) return false;
                    dp[i][j] = dp[i][j - 2];
                    if (p[j - 2] == '.' || s_i == p[j - 2]) dp[i][j] = dp[i][j] || dp[i - 1][j];
                } else if (p_j == '.') dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = (s_i == p_j) && dp[i - 1][j - 1]; // a-z
            }
        }

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

0 赞同 0 条回复

yxy 普通 2023年7月21日下午6:29

好难

class Solution {
public:

    vector<vector<int>> dp;
bool isMatch(string s, string p) {
    int sn = s.size() ; int pn = p.size() ;
    dp = vector<vector<int>>(sn+10, vector<int>(pn+10, 0));
    dp[0][0] = 1;

    for (int i = 0; i <= sn; i++) {
        for (int j = 1; j <= pn; j++) {
            if (i > 0 && p[j - 1] == '.' ) {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else if (i > 0 &&  p[j - 1] != '*'  && p[j-1] == s[i-1]) {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else if (p[j - 1] == '*') {
                //* 
                if (j > 1 && dp[i][j - 2] == 1)
                    dp[i][j] = 1;
                else if (i > 0 && j > 1 && (p[j - 2] == '.' || p[j - 2] == s[i - 1]) && dp[i - 1][j] == 1)
                    dp[i][j] = 1;
            }
        }
    }


    return dp[sn ][pn ];
}   






};

0 赞同 0 条回复

花老爷普通 2023年7月21日下午1:36

动态规划官解
时间：O(mn)
空间：O(mn)

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }

    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月20日下午10:08

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;
        //初始化第一行（s为""时，p是'*'才有可能匹配成功）
        for(int i = 1;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) {
                if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.'){
                    //两个字符相等，或者p是'.'则当前字符匹配成功
                    dp[i][j] = dp[i-1][j-1];
                }else if(p.charAt(j - 1) == '*'){   //题目保证'*'号不会是第一个字符，所以此处有j>=2
                    if(s.charAt(i - 1) != p.charAt(j - 2) && p.charAt(j - 2) != '.'){
                        //当前s不等于'*'号前面的字符，并且'*'前面不是'.'
                        //说明当前'*'无效
                        dp[i][j] = dp[i][j - 2];    //匹配0个

                    }else{
                        //当前s等于'*'号前面的字符，或者'*'前面是'.'
                        dp[i][j] = dp[i - 1][j] ||  dp[i][j - 2];
                    }
                }    
            }
        }
        return dp[m][n];
    }

}

0 赞同 0 条回复

局外人普通 2023年7月20日下午7:05

思路：动态规划——状态转移需要考虑空、非空，非空中又要考虑 ‘.’ 和 ‘*’ 两种情况
时间复杂度O(mn) 空间复杂度O(mn)

class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();

        boolean[][] dp = new boolean[n+1][m+1];

        for(int i=0; i<=n; i++){
            for(int j=0; j<=m; j++){
                if(j==0){//空串 空正则
                    dp[i][j] = (i==0);
                }else{
                    //非空情况
                    if(p.charAt(j-1)!='*'){//若非*
                        if(i>0 && (s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='.')){
                            dp[i][j] = dp[i-1][j-1];
                        }
                    }else{//若*
                        //不考虑，直接跳过
                        if(j>=2){
                            dp[i][j] |= dp[i][j-2];
                        }
                        //考虑*
                        if(i>=1 && j>=2 && (s.charAt(i-1)==p.charAt(j-2) || p.charAt(j-2)=='.')){
                            dp[i][j] |= dp[i-1][j];
                        }
                    }
                }
            }
        }
        return dp[n][m];
    }
}

0 赞同 0 条回复

Yodl. 普通 2023年7月20日下午4:47

//时间复杂度O(n*m),空间复杂度O(n*m)
class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.length();
        int m = p.length();
        vector> dp(n + 1, vector(m + 1, false));
        dp[0][0] = true;
        for (int j = 2; j <= m; j++) {
            if (p[j - 1] == '*' && dp[0][j - 2]) {
                dp[0][j] = true;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; 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] || dp[i][j - 2];
                    } else {
                        dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }
        return dp[n][m];
    }
};

0 赞同 0 条回复

Vow the vow。普通 2023年7月20日上午11:57

写不出来……自己不会推状态转移的情况

class Solution {
    public boolean isMatch(String A, String B) {
        int n = A.length();
        int m = B.length();
        boolean[][] f = new boolean[n + 1][m + 1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                //分成空正则和非空正则两种
                if (j == 0) {
                    f[i][j] = i == 0;
                } else {
                    //非空正则分为两种情况 * 和 非*
                    if (B.charAt(j - 1) != '*') {
                        if (i > 0 && (A.charAt(i - 1) == B.charAt(j - 1) || B.charAt(j - 1) == '.')) {
                            f[i][j] = f[i - 1][j - 1];
                        }
                    } else {
                        //碰到 * 了，分为看和不看两种情况
                        //不看
                        if (j >= 2) {
                            f[i][j] |= f[i][j - 2];
                        }
                        //看
                        if (i >= 1 && j >= 2 && (A.charAt(i - 1) == B.charAt(j - 2) || B.charAt(j - 2) == '.')) {
                            f[i][j] |= f[i - 1][j];
                        }
                    }
                }
            }
        }
        return f[n][m];
    }
}

0 赞同 0 条回复

怀瑾永久会员 2023年7月20日上午8:41

“`C++
bool isMatch(string s, string p) {
if (p.empty()) {
return s.empty();
}

// 模式不为空但字符串为空的情况
if (s.empty()) {
    if (p.length() >= 2 && p[1] == '*') {
        return isMatch(s, p.substr(2));
    }
    return false;
}

// 模式长度大于等于2且第二个字符是"*"
if (p.length() >= 2 && p[1] == '*') {
    if (s[0] == p[0] || p[0] == '.') {
        return isMatch(s.substr(1), p) || isMatch(s, p.substr(2));
    } else {
        return isMatch(s, p.substr(2));
    }
}

// 当前字符匹配
if (s[0] == p[0] || p[0] == '.') {
    return isMatch(s.substr(1), p.substr(1));
}

return false;

}

“`

0 赞同 0 条回复

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

共以下 11 个回答

# 回答此问题取消回复

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

共以下 11 个回答

# 回答此问题 取消回复

# 回答此问题取消回复