面试题库 › Go 后端 › 通配符匹配:? 与 * 的动态规划解法

通配符匹配:? 与 * 的动态规划解法

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

哪些公司问过

腾讯1微软1

常见岗位:Go 后端、软件开发(未写技术栈)

答案要点

  1. ? 匹配单个字符,* 匹配任意长度包括空串,要求整串匹配
  2. dp[i][j] 表示 s 前 i 个与 p 前 j 个是否匹配,dp[0][0]=true
  3. p[j-1] 为 ? 或字符相等时 dp[i][j]=dp[i-1][j-1]
  4. p[j-1] 为 * 时 dp[i][j]=dp[i][j-1] || dp[i-1][j]
  5. 时间 O(mn),空间可压缩为 O(n),也可用贪心回溯做到 O(1) 空间

易错点

面试官常见追问

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

相关面试题