支持点号和星号的正则匹配实现
哪些公司问过
答案要点
- dp[i][j] 表示 s 前 i 个字符与 p 前 j 个字符是否完全匹配,dp[0][0]=true
- 空串初始化:p[j-1] 为星号时 dp[0][j]=dp[0][j-2]
- 非星号:字符相等或为点时 dp[i][j]=dp[i-1][j-1]
- 星号:dp[i][j]=dp[i][j-2] 或(s[i-1] 与 p[j-2] 匹配且 dp[i-1][j])
- 时间 O(mn),空间可滚动到 O(n);也可递归加记忆化
易错点
- 漏掉空串初始化,导致 s 为空、p 为 a* 时判错
- 把星号当成独立的通配符,不和前一个字符绑定
- 下标混乱:dp 用长度下标,访问字符要用 i-1、j-1、j-2
面试官常见追问
- 和通配符匹配(? 和 *)有什么区别?
- 为什么匹配多次时取 dp[i-1][j] 而不是 dp[i-1][j-2]?
- 能直接用回溯吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场