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)总结正则表达式匹配使用动态规划解决核心是对 * 的处理。