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

陆狗陆狗普通 2024年12月28日上午12:05

解题思路
– a的含义是0个或者多个a
– 定义dp ,dp[i][j]，其中i>=1,j>=1，表示长度为i的s子字符串和长度为j的p字符串的时候匹配，其中dp[0][0]=true表示空白字符串
– s[i-1]和pj-1
– 如果p[j-1]是.，dp[i][j]= dp[i-1][j-1]
– 如果p[j-1]是字符，dp[i][j]= dp[i-1][j-1] && s[i-1]p[j-1]
– 如果p[j-1]是
– pChars[j – 2] != sChars[i – 1] 时（注意同时要pChars[j – 2] != ‘.’ ），dp[i][j] = dp[i][j – 2];
– pChars[j – 2] sChars[i – 1] 时
– *不表示0个pChars[j – 2]，dp[i][j] = dp[i][j – 2]
– *表示1个pChars[j – 2]，dp[i][j] = dp[i][j – 1]
– *表示多个pChars[j – 2]，dp[i][j] = dp[i – 1][j];
【题解1】

class Solution {
    public boolean articleMatch(String s, String p) {
        // a*的含义是0个或者多个a
        // 定义dp ,dp[i][j]，其中i>=1,j>=1，表示长度为i的s子字符串和长度为j的p字符串的时候匹配，其中dp[0][0]=true表示空白字符串
        // dp[i][j]如何进行表示，关键是看p[j-1](因为是下标，所以是j-1)
        // 如果p[j-1]是.或者字符，dp[i][j]= dp[i-1][j-1] && s[i-1]==p[j-1]
        // 如果p[j-1]是* 
        // *表示0个p[j-2]，dp[i][j]=dp[i]dp[j-2]
        // 表示1个p[j-2]，dp[i][j]=dp[i]dp[j-1]
        // 表示多个p[j-2]就可以无限抵消s的尾数，dp[i][j]=dp[i-1][j]
        char[] sChars = s.toCharArray();
        char[] pChars = p.toCharArray();
        // 注意，默认都是false
        // 【错误】为什么要+1，是因为要表示长度为n的字符串，那么下标就是n，那么数组长度就是n+1
        boolean[][] dp = new boolean[sChars.length + 1][pChars.length + 1];

        // 初始化（表示空字符串和空字符串匹配）
        dp[0][0] = true;
        // 初始化第0行(表示s是空字符串)
        // p=""a*""无法通过，j=2，因为j=1时是不可能出现 p="*"，不被允许的，因而dp[0][1]一定是默认值false
        for (int j = 1; j < pChars.length + 1; j++) {
            if (pChars[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }
        // 初始化第0列（表示p是空字符串，那么就是默认值false，就不需要初始化了）

        // 开始遍历
        for (int i = 1; i < sChars.length + 1; i++) {
            for (int j = 1; j < pChars.length + 1; j++) {
                if (pChars[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pChars[j - 1] == '*') {
                    // 分别*表示0个pChars[j-1]，1个pChars[j-1]，多个pChars[j-1]，只要有一个能满足即可
                    // pChars[j-2]是否和sChars[j-1]相等
                    // 【错误】 pChars[j - 2]可能是 . 所以不能直接用不相等来判断
                    if (pChars[j - 2] != '.' && pChars[j - 2] != sChars[i - 1]) {
                        dp[i][j] = dp[i][j - 2];
                    } else {
                        dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];
                    }
                } else {
                    // p是普通字符
                    // 【错误】sChars[i-1] == pChars[j-1]而不是 sChars[i] == pChars[j]，因为i和j表示的是长度
                    dp[i][j] = dp[i - 1][j - 1] && sChars[i - 1] == pChars[j - 1];
                }
            }
        }

        return dp[sChars.length][pChars.length];

    }
}

错误点1：为什么要+1，是因为要表示长度为n的字符串，那么下标就是n，那么数组长度就是n+1
错误点2：pChars[j – 2]可能是 . 所以不能直接用不相等来判断
错误点3：sChars[i-1] pChars[j-1]而不是 sChars[i] pChars[j]，因为i和j表示的是长度

0 赞同 0 条回复

Pendulumpal 普通 2024年12月25日下午8:57

递归

class Solution {
    public boolean articleMatch(String article, String input) {
        return matchHelper(article, input, 0, 0);
    }

    // 递归辅助函数
    private boolean matchHelper(String article, String input, int i, int j) {
        // 如果模式已经匹配完
        if (j == input.length()) {
            return i == article.length();
        }

        // 判断当前字符是否匹配
        boolean firstMatch = (i < article.length() && (input.charAt(j) == article.charAt(i) || input.charAt(j) == '.'));

        // 如果下一个字符是 '*'
        if (j + 1 < input.length() && input.charAt(j + 1) == '*') {
            // '*' 可以表示 "零次" 或 "多次"
            return matchHelper(article, input, i, j + 2) || (firstMatch && matchHelper(article, input, i + 1, j));
        } else {
            // 当前字符匹配的情况下递归检查下一个字符
            return firstMatch && matchHelper(article, input, i + 1, j + 1);
        }
    }
}

dp

class Solution {
    public boolean articleMatch(String article, String input) {
        // 动态规划表：dp[i][j] 表示 article 的前 i 个字符和 input 的前 j 个字符是否匹配
        int m = article.length();
        int n = input.length();
        boolean[][] dp = new boolean[m + 1][n + 1];

        // 基础情况：空的 article 和空的 input 是匹配的
        dp[0][0] = true;

        // 处理像 a*，a*b* 等模式可以与空的 article 匹配的情况
        for (int j = 1; j <= n; j++) {
            if (input.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2]; // '*' 可以表示 "前一个元素出现零次"
            }
        }

        // 填充动态规划表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char articleChar = article.charAt(i - 1);
                char inputChar = input.charAt(j - 1);

                if (inputChar == '.' || inputChar == articleChar) {
                    // 当前字符匹配
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (inputChar == '*') {
                    // '*' 可以表示 "前一个元素出现零次或多次"
                    char precedingChar = input.charAt(j - 2);
                    dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (precedingChar == '.' || precedingChar == articleChar));
                } else {
                    // 当前字符不匹配
                    dp[i][j] = false;
                }
            }
        }

        // 结果存储在 dp[m][n] 中
        return dp[m][n];
    }
}

0 赞同 0 条回复

Kisara 普通 2024年12月24日上午10:42

执行用时1ms击败100.00%(gpt的思路）

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 j=1;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)=='.'||p.charAt(j-1)==s.charAt(i-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else if(p.charAt(j-1)=='*'){
                    dp[i][j]=dp[i][j-2];
                    if(p.charAt(j-2)==s.charAt(i-1)||p.charAt(j-2)=='.'){
                        dp[i][j]=dp[i][j]||dp[i-1][j];
                    }
                }
            }
        }

        return dp[m][n];
    }
}

OMxN  OMxN

0 赞同 0 条回复

苯庸普通 2024年12月24日上午10:18

class Solution {
public boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
// dp[i][j] 代表字符串 s 的前 i 个字符和 p 的前 j 个字符能否匹配。
boolean[][] dp = new boolean[m+1][n+1];
dp[0][0] = true;
for(int j = 2; j <= n; j += 2){
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) ‘‘){
// s: a p: a* 消除p s:abb p: ab* 消除s s:abb p: a.* 消除s
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{
dp[i][j] = (dp[i-1][j-1] && p.charAt(j-1) ‘.’) || (dp[i-1][j-1] && p.charAt(j-1) s.charAt(i-1));
}

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

}
时间：O（mn）
空间：O（mn）

0 赞同 0 条回复

Aatorx 永久会员 2024年12月23日下午4:33

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

时间复杂度O(Mn)，空间复杂度O(Mn)。

0 赞同 0 条回复

月下足迹普通 2024年12月22日上午11:23

//放弃
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];
}

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 条回复

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

共以下 6 个回答

# 回答此问题取消回复

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

共以下 6 个回答

# 回答此问题 取消回复

# 回答此问题取消回复