LeetCode 10：正则表达式匹配 | 动态规划

LeetCode 10：正则表达式匹配 | 动态规划

引言

正则表达式匹配（Regular Expression Matching）是 LeetCode 第 10 题，难度为 Hard。题目要求实现正则表达式匹配，支持 '.' 和 '*'。

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

算法实现

Python 实现

def isMatch(s, p): m, n = len(s), len(p) dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True for j in range(1, n + 1): if p[j - 1] == '*': dp[0][j] = dp[0][j - 2] for i in range(1, m + 1): for j in range(1, n + 1): if p[j - 1] == '*': dp[i][j] = dp[i][j - 2] if p[j - 2] == '.' or p[j - 2] == s[i - 1]: dp[i][j] = dp[i][j] or dp[i - 1][j] elif p[j - 1] == '.' or p[j - 1] == s[i - 1]: dp[i][j] = dp[i - 1][j - 1] return dp[m][n]

复杂度分析

时间复杂度：O(m * n)
空间复杂度：O(m * n)

总结

正则表达式匹配使用动态规划解决，核心是对 '*' 的处理。