每日一题｜剑指Offer地狱级难题！正则表达式匹配，你能扛住吗？

🌟每日一题｜剑指Offer地狱级难题！正则表达式匹配，你能扛住吗？🌟

💡题目描述

《剑指Offer 19. 正则表达式匹配》
请实现一个函数用来匹配包含'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，'*'表示它前面的字符可以出现任意次（含0次）。例如，字符串"aaa"与模式"a.a"或"ab*ac*a"匹配，但与"aa.a"或"ab*a"不匹配。

难度：⭐⭐⭐⭐⭐（地狱级动态规划）

🚨核心提示

1️⃣ 动态规划是本题的最优解方向
2️⃣ 注意'*'的特殊性：它必须和前面的字符组合使用
3️⃣ 分情况讨论：当前字符是否匹配？下一个字符是否是'*'？

🧠解题思路拆解

Step 1：定义状态
dp[i][j]表示字符串s的前i个字符与模式p的前j个字符是否匹配。

Step 2：初始化

• dp[0][0] = true：空字符串匹配空模式
• 处理模式中'*'开头的情况：如a*b*c*可能匹配空字符串

Step 3：状态转移

• Case 1：p[j-1] != '*'
  当前字符必须匹配：s[i-1] == p[j-1]或p[j-1] == '.'
  且之前的结果也必须匹配：dp[i][j] = dp[i-1][j-1]

• Case 2：p[j-1] == '*'

  • 子情况1：*匹配0次 → 丢弃x*组合：dp[i][j] = dp[i][j-2]
  • 子情况2：*匹配≥1次 → 必须满足当前字符匹配，且字符串前移：dp[i][j] = dp[i-1][j]

Step 4：处理边界

• 当s为空时，模式必须类似a*b*的形式才能匹配

🚀代码实现（Java）

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;

        // 初始化第一行（s为空字符串的情况）
        for(int j=2; j<=n; j+=2) {
            if(p.charAt(j-1) == '*' && dp[0][j-2]) {
                dp[0][j] = true;
            }
        }

        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                char sc = s.charAt(i-1);
                char pc = p.charAt(j-1);

                if(pc != '*') {
                    if(sc == pc || pc == '.') {
                        dp[i][j] = dp[i-1][j-1];
                    }
                } else {
                    // 处理 '*' 的情况
                    if(j >= 2) {
                        // 选择匹配0次 或 匹配多次
                        dp[i][j] = dp[i][j-2] || 
                            ((sc == p.charAt(j-2) || p.charAt(j-2) == '.') && dp[i-1][j]);
                    }
                }
            }
        }
        return dp[m][n];
    }
}

🧠测试用例

• Case 1：s="aa", p="a*" → true
• Case 2：s="ab", p=".*" → true（.*匹配任意字符串）
• Case 3：s="", p="a*b*c*" → true

📌灵魂拷问

• Q：为什么不用递归而用动态规划？
  A：递归时间复杂度爆炸（指数级），动态规划将复杂度优化到O(mn)

• Q：如何处理a*匹配零次的情况？
  A：直接跳过这两个字符（即dp[i][j] = dp[i][j-2]）

💬 评论区互动
“你在面试中遇到过这道题吗？花了多久AC的？欢迎晒出你的解题经历！” 🔥