LeetCode 44：通配符匹配 | 动态规划

LeetCode 44通配符匹配 | 动态规划引言通配符匹配Wildcard Matching是 LeetCode 第 44 题难度为 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 - 1] for i in range(1, m 1): for j in range(1, n 1): if p[j - 1] *: dp[i][j] dp[i][j - 1] 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)总结通配符匹配与正则表达式匹配类似但 的语义不同 可以匹配任意序列。