一.题目描述
给你一个字符串 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 <= 201 <= p.length <= 20s只包含从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];}// 初始化匹配结果为 falseboolean 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 是否也匹配完。·记忆化搜索：如果当前状态已计算过，直接返回结果。·处理 '' 通配符：* 可以匹配零个或多个前面的字符。·处理普通字符和 '.' 通配符：检查当前字符是否匹配，并递归检查下一个字符。·返回结果：记录并返回当前状态的匹配结果。
