当前位置：首页 > article >正文

LeetCode-正则表达式匹配（010）

article 2025/1/3 5:05:28

一.题目描述

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。

二.示例

示例 1：

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2：

输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：

输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

三.提示：

1 <= s.length <= 20
1 <= p.length <= 20
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

四.解法:

方法一：记忆化搜索

我们设计一个函数 dfs(i,j)，表示从 s 的第 i 个字符开始，和 p 的第 j 个字符开始是否匹配。那么答案就是 dfs(0,0)。

函数 dfs(i,j) 的计算过程如下：

如果 j 已经到达 p 的末尾，那么如果 i 也到达了 s 的末尾，那么匹配成功，否则匹配失败。
如果 j 的下一个字符是 '*'，我们可以选择匹配 0 个 s[i] 字符，那么就是 dfs(i,j+2)。如果此时 i<m 并且 s[i] 和 p[j] 匹配，那么我们可以选择匹配 1 个 s[i] 字符，那么就是 dfs(i+1,j)。
如果 j 的下一个字符不是 '*'，那么如果 i<m 并且 s[i] 和 p[j] 匹配，那么就是 dfs(i+1,j+1)。否则匹配失败。

过程中，我们可以使用记忆化搜索，避免重复计算。

时间复杂度 O(m×n)，空间复杂度 O(m×n)。其中 m 和 n 分别是 s 和 p 的长度。

五.代码

Java代码

class Solution {
    // 定义类成员变量，用于存储匹配状态、输入字符串和模式字符串及其长度
    private Boolean[][] f;
    private String s;
    private String p;
    private int m;
    private int n;

    public boolean isMatch(String s, String p) {
        // 获取输入字符串和模式字符串的长度
        m = s.length();
        n = p.length();
        // 初始化匹配状态数组，大小为 (m+1) x (n+1)
        f = new Boolean[m + 1][n + 1];
        // 将输入字符串和模式字符串赋值给类成员变量
        this.s = s;
        this.p = p;
        // 调用深度优先搜索函数，从起始位置开始匹配
        return dfs(0, 0);
    }

    private boolean dfs(int i, int j) {
        // 如果模式字符串已匹配完，检查输入字符串是否也匹配完
        if (j >= n) {
            return i == m;
        }
        // 如果当前状态已计算过，直接返回结果
        if (f[i][j] != null) {
            return f[i][j];
        }
        // 初始化匹配结果为 false
        boolean res = false;
        // 处理 '*' 通配符的情况
        if (j + 1 < n && p.charAt(j + 1) == '*') {
            // '*' 可以匹配零个或多个前面的字符
            res = dfs(i, j + 2) // 匹配零个字符
                || (i < m && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') && dfs(i + 1, j)); // 匹配一个或多个字符
        } else {
            // 处理普通字符和 '.' 通配符的情况
            res = i < m && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') && dfs(i + 1, j + 1);
        }
        // 记录当前状态的匹配结果
        return f[i][j] = res;
    }
}

注释说明
    ·类成员变量：用于存储匹配状态 f、输入字符串 s、模式字符串 p 及其长度 m 和 n。
    ·isMatch 方法：初始化变量并调用 dfs 函数进行匹配。
    ·dfs 函数：递归地检查字符串 s 和模式 p 是否匹配。
        ·终止条件：如果模式字符串 p 已匹配完，检查输入字符串 s 是否也匹配完。
        ·记忆化搜索：如果当前状态已计算过，直接返回结果。
        ·处理 '' 通配符：* 可以匹配零个或多个前面的字符。
        ·处理普通字符和 '.' 通配符：检查当前字符是否匹配，并递归检查下一个字符。
    ·返回结果：记录并返回当前状态的匹配结果。