P44 通配符匹配
本文讲解力扣第44题“通配符匹配”,是一道典型的线性动态规划问题。给定字符串 `s` 和模式串 `p`,其中 `p` 包含普通字符、`?`(匹配任意单个字符)和 `*`(匹配任意字符串,包括空串),判断两者是否完全匹配。解法使用二维DP数组 `f[i][j]` 表示 `s` 的前 `i` 个字符与 `p` 的前 `j` 个字符是否匹配。初始化时考虑 `*` 可匹配空串,状态转移分三种情况:当 `p[j-1]` 为 `*` 时,可继承 `f[i][j-1]` 或 `f[i-1][j]`;否则若字符相等或为 `?`,则依赖 `f[i-1][j-1]`。最终结果为 `f[n][m]`。代码清晰地实现了该逻辑,时间复杂度为 O(nm)。