👤作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。
会一些的技术:数据分析、算法、SQL、大数据相关、python欢迎加入社区:码上找工作http://t.csdnimg.cn/Q59WX
作者专栏每日更新:
LeetCode解锁1000题: 打怪升级之旅LeetCode解锁1000题: 打怪升级之旅https://blog.csdn.net/cciehl/category_12625714.html
python数据分析可视化:企业实战案例https://blog.csdn.net/cciehl/category_12615648.html
备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级
题目描述
给你一个字符串 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
的小写字母,以及字符.
和*
。- 保证每次出现字符
*
时,前面都匹配到有效的字符
解题思路
方法一:递归
递归方法是理解这个问题的一个很好的起点,它可以直观地将问题分解为更小的子问题来解决。
解题步骤
1. 基本情况:如果模式 p
为空,成功匹配取决于字符串 s
也为空。
2. 匹配第一个字符:检查 s
和 p
的第一个字符是否匹配(考虑到 '.'
)。
3. 使用 '*'
:如果 p
的第二个字符是 '*'
,则有两种情况:
- 我们跳过
'*'
和它之前的字符,因为'*'
可以匹配零个字符; - 如果第一个字符匹配,移动字符串
s
,因为'*'
可以匹配多个字符。
4. 递归匹配剩余字符串:根据以上逻辑递归地匹配剩余的 s
和 p
。
python示例
def isMatch(s: str, p: str) -> bool:
# 如果模式为空,成功匹配取决于字符串也为空
if not p:
return not s
# 检查s的第一个字符是否与p的第一个字符匹配
first_match = bool(s) and p[0] in {s[0], '.'}
# 如果p的长度大于1并且p的第二个字符是'*'
if len(p) >= 2 and p[1] == '*':
# 使用'*'匹配0个字符,或者第一个字符匹配且s向前移动一位
return (isMatch(s, p[2:])) or first_match and isMatch(s[1:], p)
else:
# 如果没有'*',则直接移动s和p都向前移动一位
return first_match and isMatch(s[1:], p[1:])
# 示例测试
print(isMatch("aa", "a*")) # True
print(isMatch("mississippi", "mis*is*p*.")) # False
方法二:动态规划
动态规划是解决这个问题的关键方法,它可以有效地避免重复计算,并且处理复杂的 '*'
匹配规则。
解题步骤
1. 初始化DP表:创建一个 (len(s) + 1) x (len(p) + 1)
大小的二维列表 dp
。dp[i][j]
表示字符串 s
的前 i
个字符与模式 p
的前 j
个字符是否能够匹配。初始化所有元素为 False
。
2. 基础情况:空字符串和空模式是匹配的,因此 dp[0][0] = True
。然后初始化模式 p
中连续的 '*'
对应的状态,因为 '*'
可以取消前一个字符
3. 填充DP表:遍历 s
和 p
,对每一对字符更新 dp[i][j]
:
- 如果
p[j-1]
是'*'
,则有两种情况:'*'
取消前一个字符(即模式p
跳过两个字符),这时dp[i][j]
取决于dp[i][j-2]
;- 使用
'*'
匹配s
中的多个字符,这时如果s[i-1]
与p[j-2]
匹配,dp[i][j]
取决于dp[i-1][j]
。
- 如果
p[j-1]
是'.'
或者s[i-1]
与p[j-1]
相等,dp[i][j]
取决于dp[i-1][j-1]
。
4. 返回结果:表格的最后一个元素 dp[-1][-1]
表示整个字符串 s
与模式 p
是否匹配。
python示例
def isMatch(s: str, p: str) -> bool:
# 初始化DP表,dp[i][j]表示s的前i个字符与p的前j个字符是否匹配
dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
# 空字符串与空模式是匹配的
dp[0][0] = True
# 处理模式p的前缀为'*'的情况
for j in range(1, len(p) + 1):
if p[j-1] == '*':
dp[0][j] = dp[0][j-2]
# 填充DP表
for i in range(1, len(s) + 1):
for j in range(1, len(p) + 1):
# 当前模式字符为'*'
if p[j-1] == '*':
dp[i][j] = dp[i][j-2] or (dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))
# 当前模式字符为'.'或者与字符串字符相同
else:
dp[i][j] = dp[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '.')
return dp[-1][-1]
优缺点
- 优点:
- 动态规划避免了重复计算,大大提高了效率;
- 明确地定义了所有状态转移情况,使得算法具有良好的结构性和可读性。
- 缺点:
- 动态规划的空间复杂度较高,特别是当
s
和p
长度较大时; - 对于初学者来说,理解动态规划的状态转移可能稍显复杂。
- 动态规划的空间复杂度较高,特别是当