题目
给你一个字符串 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 <= 20-
s只包含从a-z的小写字母。 -
p只包含从a-z的小写字母，以及字符.和*。 - 保证每次出现字符
*时，前面都匹配到有效的字符
解题思路
最初的方法 是使用递归或者回溯算法，从字符串和模式的开头开始一对一匹配字符，遇到 '*' 时进行特殊处理。然而，这种方法在处理复杂模式或长字符串时可能会遇到性能瓶颈。
class Solution:
def isMatch(self, s: str, p: str) -> bool:
if not p:
return not s
first_match = bool(s) and p[0] in {s[0], '.'}
if len(p) >= 2 and p[1] == '*':
return (self.isMatch(s, p[2:]) or
first_match and self.isMatch(s[1:], p))
else:
return first_match and self.isMatch(s[1:], p[1:])
优化方法
为了提高效率，动态规划 是解决这类问题的理想选择。我们定义一个二维数组 dp，其中 dp[i][j] 表示字符串 s 的前 i 个字符和模式 p 的前 j 个字符是否匹配。通过填充这个二维表格，我们可以避免重复计算，并利用之前的结果来解决当前的子问题。
class Solution:
def isMatch(self, s: str, p: str) -> bool:
# 使用动态规划，dp[i][j] 表示s的前i个字符与p的前j个字符是否能匹配
dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
# 空字符串与空模式是匹配的
dp[0][0] = True
# 处理模式p的前j个字符与空字符串s的匹配情况
for j in range(2, len(p) + 1):
dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'
for i in range(1, len(s) + 1):
for j in range(1, len(p) + 1):
if p[j - 1] == '*':
# '*' 匹配0个或多个前面的元素
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]
运行
sol = Solution()
print(sol.isMatch("aa", "a")) # False
print(sol.isMatch("aa", "a*")) # True
print(sol.isMatch("ab", ".*")) # True
总结
本文讨论了如何使用最初的递归方法以及优化后的动态规划方法来解决正则表达式匹配的问题。通过比较两种方法，我们可以看到动态规划在处理这类匹配问题时提供了显著的性能优势。优化后的动态规划方法不仅更加高效，还能更好地处理复杂的模式匹配情况，特别是在模式中包含多个 '*' 和 '.' 字符时。因此，当面对需要匹配大量数据的情况时，选择动态规划作为解决方案将是一个明智的决策。
