当前位置：
  1. 首页
  2. 剑指offer刷题第五期
  3. 问题详情

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

本问题对应课程链接：剑指offer刷题第五期

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi
67 2

共以下 2 个回答

  • 别扒拉我 普通 2023年9月15日 上午10:43

    记录一下

    class Solution {
    public boolean isMatch(String s, String p) {
    if(p.isEmpty()){
        return s.isEmpty();
    }
    boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
    dp[s.length()][p.length()] = true;
    for (int i = s.length(); i >= 0; i--) {
        for (int j = p.length() - 1; j >= 0; j--) {
            boolean flag = j + 1 < p.length() && p.charAt(j + 1) == '*';
            if (i == s.length()) {
                if (flag) dp[i][j] = dp[i][j + 2];
            }else {
                boolean first_match = s.charAt(i) == p.charAt(j) || p.charAt(j) == '.';
                if (flag){
                    dp[i][j] = (first_match && dp[i + 1][j]) || dp[i][j + 2];
                }else{
                    dp[i][j] = first_match && dp[i + 1][j + 1];
                }
            }
        }
    }
    return dp[0][0];
}
}
    0 赞同 0 条回复
  • 塔底的仰望 永久会员 2023年9月14日 下午10:30

    好难。。。

    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=2开始考虑，因为这种情况下不可能进入else
                // 当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为*
                    // 第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];
    }
}
    0 赞同 0 条回复

# 回答此问题

后才能回答