📃 题目描述

题目链接：剑指 Offer 19. 正则表达式匹配 (opens new window)

🔔 解题思路

具体思路参考 https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solution/zheng-ze-biao-da-shi-pi-pei-by-leetcode-s3jgn/

class Solution {
    public boolean isMatch(String s, String p) {
        int len1 = s.length();
        int len2 = p.length();

        // dp[i][j] 表示 p[0...j - 1] 能否匹配 s[0...i - 1]
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        dp[0][0] = true;

        for (int i = 0; i <= len1; i ++) {
            for (int j = 1; j <= len2; j ++) {
                // 1. p 的当前字符是 *
                if (p.charAt(j - 1) == '*') {
                    // p[j - 2] 能否匹配 s[i - 1]
                    if (match(s, p, i - 1, j - 2)) {
                        // 匹配多次或者匹配 0 次
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
                    }
                    else {
                        dp[i][j] = dp[i][j - 2];
                    }
                }
                // 2. p 的当前字符是字母或者 .
                else {
                    if (match(s, p, i - 1, j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                    else {
                        dp[i][j] = false;
                    }
                }
            }
        }

        return dp[len1][len2];
    }

    // p[j] 能否匹配 s[i]
    private boolean match(String s, String p, int i, int j) {
        if (i < 0) {
            return false;
        }

        // . 可以表示任意一个字符
        if (p.charAt(j) == '.') {
            return true;
        }

        return s.charAt(i) == p.charAt(j);
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：