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

Thaddeus 永久会员 2024年5月6日下午3:10

打卡

class Solution {
    public boolean articleMatch(String s, String p) {
        int n = s.length(), 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 - 1][j - 2] || dp[i - 1][j];
                }
            }
        }
        return dp[n][m];
    }
}

0 赞同 0 条回复

方铎码农普通 2024年4月8日下午3:01

class Solution {
    public boolean articleMatch(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];
    }

    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);
    }
}

时间复杂度$O(mn)$,空间复杂度$O(mn)$

0 赞同 0 条回复

Jimmy 普通 2024年4月3日下午6:49

时间复杂度：O(nm)
空间复杂度：O(nm)

class Solution {
public:
    bool articleMatch(string s, string p) {
        int n = s.size();
        int m = p.size();
        vector<vector<bool>> f = vector(n+1,vector(m+1,false));

        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<m;j++)
            {
                //分成空正则还是非空正则
                if(j == 0)//空正则
                {
                    f[i][j] = i == 0;
                }
                else//非空正则
                {
                    //非空正则分为*和非*
                    if(p[j-1] != '*')
                    {
                        if(i>0 && (s[i-1] == p[j-1] || p[j-2] == '.')) f[i][j] = f[i-1][j-1];
                    }
                    else
                    {
                        //如果是遇到了*，分为两种情况
                        // 1. 不看 直接砍掉正则串的后面两个
                        if(j>=2) f[i][j] = f[i][j-2];
                        // 2. 正则串不动，主串前移一个
                        if(i>=1 && j>=2 && (s[i-1] == p[j-2] || p[j-2] == '.')) f[i][j] = f[i][j] || f[i-1][j];
                    }
                }
            }
        }
        return f[n][m];
    }

};

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年4月3日下午6:42

class Solution {
    public boolean articleMatch(String s, String p) {
        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{
                    // 如果是 *
                    // 匹配0个
                    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-1][j-2] || dp[i-1][j];
                    }
                }
            }
        }
        return dp[n][m];
    }
}

时间复杂度：O(nm)
空间复杂度：O(nm)

0 赞同 0 条回复

heathhou 普通 2024年4月2日下午8:13

class Solution {
public:
    bool articleMatch(string s, string p) {
        int n = s.length();
        int m = p.length();

        // dp: 当字符串的长度分别为i,j的时候，是否匹配
        vector<vector<bool>> dp(n+1, vector<bool>(m+1, false));

        // 初始化
        dp[0][0] = true;
        dp[0][1] = false;
        for(int j = 2; j <= m; ++j){
            if(p[j-1] == '*'){
                dp[0][j] = dp[0][j-2];
            }
        }

        // 根据dp方程来推导
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= m; ++j){
                // 当p的第j个字符 不为 *
                if(p[j-1] != '*'){
                    if(p[j-1] == '.' || p[j-1] == s[i-1]){
                        dp[i][j] = dp[i-1][j-1];
                    }
                }
                // 当p的第j个字符 为 *
                else{
                    // 当p的第j-1个字符不匹配
                    if(p[j-2] != s[i-1] && p[j-2] != '.'){
                        dp[i][j] = dp[i][j-2];
                    }
                    // 当p的第j-1个字符匹配
                    else{
                        dp[i][j] = dp[i][j-2] || dp[i][j-1] || dp[i-1][j];
                    }
                }
            }
        }
        return dp[n][m];
    }
};

0 赞同 0 条回复

紫芝普通 2024年4月2日上午9:18

动态规划：dp[i][j]表示 s 的前 i 个字符串和 p 的前 j 个字符串是否匹配。
在匹配字符串的时候有几种情况需要考虑：
p[j] ‘‘: 可以匹配 p[j-1] 0次或多次
p[j] != ‘‘: 直接比较p[j]‘.’ || s[i]p[j]
在初始化 dp 的时候有几种情况需要考虑：
空字符串，空模式串：dp[0][0] = true
空字符串，非空模式串：dp[0][j]: 只有当 p[j]‘*’时，dp[0][j] = dp[0][j-2]; 其余情况 dp[0][j] = false;
非空字符串，空模式串：dp[i][0] = true;
非空字符串，非空模式串：计算dp[i][j]
最后返回 dp[s.size()][p.size()] 的结果即可

“`c++
class Solution {
public:
bool articleMatch(string s, string p) {
int n = s.size(), m = p.size();
if (m == 0) {
return n == 0 ? true : false;
}
// dp[n][0] = false
vector> dp(n+1, vector(m+1, false));
dp[0][0] = true;
// dp[0][m]: only c* can make dp[0][j] = true, other dp[0][j] = false
for (int j=1; j<=m; j++) { if (p[j-1] == '*') { if (j >= 2) dp[0][j] = dp[0][j-2];
else dp[0][j] = false;
} else {
dp[0][j] = false;
}
}
for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) { if (p[j-1] != '*') { if (p[j-1] == '.' || s[i-1] == p[j-1]) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = false; } else { if (dp[i][j-2] == true) dp[i][j] = true; else if (s[i-1] == p[j-2] || p[j-2] == '.') dp[i][j] = dp[i-1][j]; else dp[i][j] = false; } } } return dp[n][m]; ```

0 赞同 0 条回复

云无深雁影普通 2024年4月1日下午10:53

//递归
class Solution {
public boolean articleMatch(String s, String p) {
return articleMatch(s,p,0,0);
}
private boolean articleMatch(String s,String p ,int ptr1,int ptr2){
//System.out.println(“ptr1=”+ptr1+” ptr2=”+ptr2);
if(s.length() ptr1 && p.length() ptr2) return true;//两指针同时到终点
else if(p.length() ptr2) return false;//p已遍历完s没遍历完
else if (s.length() ptr1)//s遍历完p没遍历完
{
if(ptr2 < p.length() && p.charAt(ptr2) ‘‘)//如果p的剩余部分为，则跳过该部分再判断
return articleMatch(s,p,ptr1,ptr2+1);
if(ptr2+1 < p.length() && p.charAt(ptr2+1) ‘‘)//如果p的剩余部分为a，则跳过该部分再判断
return articleMatch(s,p,ptr1,ptr2+2);
return false;
}
// if(s.charAt(ptr1) != p.charAt(ptr2) && p.charAt(ptr2)!=’.’ && p.charAt(ptr2)!=’‘)//或许可删
// return false;
if(s.charAt(ptr1) p.charAt(ptr2) || p.charAt(ptr2) ‘.’){
if(ptr2+1 < p.length() && p.charAt(ptr2+1)‘‘)//即使匹配上，若p的下一位为*，则有可能不消除
return articleMatch(s,p,ptr1+1,ptr2+1) || articleMatch(s,p,ptr1,ptr2+2);
return articleMatch(s,p,ptr1+1,ptr2+1);
}

    if(p.charAt(ptr2) == '*'){
        boolean b = false;
        for(int i = ptr1; i <= s.length(); i++){
            if(p.charAt(ptr2-1) == s.charAt(i-1) || p.charAt(ptr2-1)=='.')
                b = b || articleMatch(s,p,i,ptr2+1);
            else
                break;
        }
        return b;
    }
    if(ptr2+1 < p.length() && p.charAt(ptr2+1) == '*')
        return articleMatch(s,p,ptr1,ptr2+2);
    return false;
}

}

//
class Solution {
public boolean articleMatch(String s, String p) {
boolean[][] dp = new boolean[s.length()+1][p.length()+1];

    for(int i = 0; i <= s.length();i++){
        for(int j = 0; j <= p.length(); j++){
            if(j == 0 )
                dp[i][j] = i==0;
            else{
                if(p.charAt(j-1) != '*' && i > 0 && (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-1) == '*'){
                    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];
                }
                else
                    dp[i][j] = false;
            }
        }
    }
    return dp[s.length()][p.length()];
}

}
//动态规划

0 赞同 0 条回复

王位詮釋普通 2024年4月1日下午7:54

class Solution {
    public boolean articleMatch(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 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++){
                //当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{
                    //第i个字符不匹配
                    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 条回复

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

共以下 8 个回答

# 回答此问题取消回复

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

共以下 8 个回答

# 回答此问题 取消回复

# 回答此问题取消回复