面试题库 › Java 后端 › 支持点号和星号的正则匹配实现

支持点号和星号的正则匹配实现

难度 ★★★在 1 场真实面经中被问到 方向:Java 后端考点:动态规划

哪些公司问过

微软1

常见岗位:Java 后端

答案要点

  1. dp[i][j] 表示 s 前 i 个字符与 p 前 j 个字符是否完全匹配,dp[0][0]=true
  2. 空串初始化:p[j-1] 为星号时 dp[0][j]=dp[0][j-2]
  3. 非星号:字符相等或为点时 dp[i][j]=dp[i-1][j-1]
  4. 星号:dp[i][j]=dp[i][j-2] 或(s[i-1] 与 p[j-2] 匹配且 dp[i-1][j])
  5. 时间 O(mn),空间可滚动到 O(n);也可递归加记忆化

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题