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

hi 普通 2023年11月27日下午4:29

dp[i][j]为s 中前i 个字母与p 中前j 个字母是否能匹配，按是否有’*’ 来分类
如果该字母的下个字母为’*’，当前字母就不看作一个完整的字母

class Solution {
public:
    bool articleMatch(string s, string p) {
        s = ' ' + s, p = ' ' + p;
        int n = s.size(), m = p.size();
        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1)); //默认为false
        dp[0][0] = true;

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

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

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

0 赞同 0 条回复

June 普通 2023年11月6日下午6:38

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[i][j] 表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配
        dp[0][0] = true;
        for(int i=0;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(p.charAt(j-1) == '*')
                {
                    dp[i][j] = dp[i][j-2];
                    if(matches(s,p,i,j-1))
                    {
                        dp[i][j] = dp[i][j] || dp[i-1][j];
                    }
                }
                else
                {
                    if(matches(s,p,i,j))
                        dp[i][j] = dp[i-1][j-1];
                }
            }
        }
        return dp[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 条回复

Marshan 普通 2023年9月1日下午2:05

class Solution {
public:
    bool isMatch(string s, string p) {
        // 情况是真的多啊
        int n = s.size();
        int m = p.size();

        vector<vector<bool>> dp(n+1,vector<bool>(m+1,false));
        // dp[i][j]表示长度i的s和长度j的p是否匹配
        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];
            }
        }

        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{
                    if(p[j-2] != s[i-1] && p[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];
    }
};

0 赞同 0 条回复

Mby 普通 2023年8月21日下午3:38

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++){
                //当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{
                //第j - 1 个字符不匹配
                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(nm)
        //空间复杂度：O(nm)
    }
}

0 赞同 0 条回复

人生何处不青山普通 2023年8月20日下午10:52

背

function isMatch(s: string, p: string): boolean {
    let m = s.length, n = p.length;
    let dp = new Array(m + 1).fill(0).map(v => new Array(n + 1).fill(false));

    dp[0][0] = true;
    for (let i = 2; i <= n; i++) {
        if (p.charAt(i - 1) === '*') dp[0][i] = dp[0][i - 2];
    }
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p.charAt(j - 1) === '*') {
                dp[i][j] = dp[i][j - 2] || ((s.charAt(i - 1) === p.charAt(j - 2) || p.charAt(j - 2) === '.') && dp[i - 1][j]);
            } else {
                dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i - 1) === p.charAt(j - 1) || p.charAt(j - 1) === '.');
            }
        }
    }
    return dp[m][n];
};

0 赞同 0 条回复

阿尚普通 2023年8月7日下午7:49

public boolean isMatch(String s, String p) {
    char[] cs = s.toCharArray();
    char[] cp = p.toCharArray();

    // dp[i][j]:表示s[0 ~ i-1]，p[0 ~ j-1]是否能够匹配
    boolean[][] dp = new boolean[cs.length + 1][cp.length + 1];

    // 初期值
    // s为空，p为空，能匹配上
    dp[0][0] = true;
    // p为空，s不为空，必为false(boolean数组默认值为false，无需处理)
    // s为空，p不为空，由于*可以匹配0个字符，所以有可能为true
    for (int j = 2; j <= cp.length; j++) {
        if (cp[j - 1] == '*') {
            dp[0][j] = dp[0][j - 2];//匹配0次，相当于消除 * 前一个字符
        }
    }

    // 填格子
    for (int i = 1; i <= cs.length; i++) {
        for (int j = 1; j <= cp.length; j++) {
            // 文本串和模式串末位字符能匹配上
            if (cs[i - 1] == cp[j - 1] || cp[j - 1] == '.') {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (cp[j - 1] == '*') { // 模式串末位是*
                // 模式串*的前一个字符能够跟文本串的末位匹配上
                if (cs[i - 1] == cp[j - 2] || cp[j - 2] == '.') {
                    dp[i][j] = dp[i][j - 2]      // * 匹配0次的情况，相当于消除 * 前一个字符
                            || dp[i - 1][j];     // * 匹配1次或多次的情况，相当于复制 * 前一个字符一次或多次
                } else { // 模式串*的前一个字符不能够跟文本串的末位匹配
                    dp[i][j] = dp[i][j - 2];     // *只能匹配0次
                }
            }
        }
    }

    return dp[cs.length][cp.length];
}

0 赞同 0 条回复

长河呼叫黄江普通 2023年8月7日下午7:34

8.7
Day28：下面是代码

class Solution {
    public boolean isMatch(String A, String B) {
        //开数组开到n + 1，对空串处理方便。
        //定义字符串A，模式B
        int n = A.length(), 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[n][m]时进行判断。若空串（n == 0）则返回true，否则false
                    f[i][j] = i == 0;
                }else{
                    //非空正则
                    //非*
                    if(B.charAt(j - 1) != '*'){
                        if(i > 0 && (B.charAt(j - 1) == A.charAt(i - 1) || B.charAt(j - 1) == '.'))
                            f[i][j] = f[i - 1][j -1];
                    }else{
                        //*
                        //不看'ch'*
                        //使用|=  因为这是'*'下的两种子情况，|=可以将这两种子情况合并为一个最终的匹配结果
                        if(j >= 2){
                            f[i][j] |= f[i][j - 2];
                        }
                        //看'ch'*
                        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 条回复

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

共以下 7 个回答

# 回答此问题取消回复

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

共以下 7 个回答

# 回答此问题 取消回复

# 回答此问题取消回复