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)

总结

通配符匹配与正则表达式匹配类似，但 '' 的语义不同：'' 可以匹配任意序列。