通配符匹配(LeetCode 44)
哪些公司问过
答案要点
- dp[i][j]:s 前 i 个字符与 p 前 j 个字符是否匹配,dp[0][0] = true
- 初始化:dp[0][j] 仅当 p 前 j 个全为 * 时为真
- 转移:? 或字符相等取 dp[i-1][j-1];* 取 dp[i][j-1](匹配空)或 dp[i-1][j](多匹配一个)
- 复杂度 O(mn),滚动数组可降为 O(n) 空间;连续 * 可合并
- 贪心双指针:记录最近的 * 位置,失配时回退让 * 多匹配一个字符
易错点
- 忘记初始化 dp[0][j],导致 p 以 * 开头时匹配空串失败
- 把 * 的转移写成 dp[i-1][j-1],漏掉匹配空串和多个字符的情况
- 与 LC10 正则匹配的 * 语义混淆
面试官常见追问
- 和正则表达式匹配(LC10)有什么区别?
- 贪心双指针为什么正确?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场