通配符匹配:? 与 * 的动态规划解法
哪些公司问过
答案要点
- ? 匹配单个字符,* 匹配任意长度包括空串,要求整串匹配
- dp[i][j] 表示 s 前 i 个与 p 前 j 个是否匹配,dp[0][0]=true
- p[j-1] 为 ? 或字符相等时 dp[i][j]=dp[i-1][j-1]
- p[j-1] 为 * 时 dp[i][j]=dp[i][j-1] || dp[i-1][j]
- 时间 O(mn),空间可压缩为 O(n),也可用贪心回溯做到 O(1) 空间
易错点
- dp[0][j] 初始化错误,没处理模式开头连续的 *
- 处理 * 时只考虑匹配空串或只考虑匹配一个字符
- 和 LC10 正则匹配混淆,把 * 当作重复前一个字符
面试官常见追问
- 空间复杂度怎么优化?
- 贪心双指针解法怎么做?
- 和正则表达式匹配(LC10)有什么区别?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场