面试题库 › 算法 / 大模型 › 通配符匹配(LeetCode 44)

通配符匹配(LeetCode 44)

难度 ★★★在 1 场真实面经中被问到 方向:算法 / 大模型考点:动态规划

哪些公司问过

字节跳动1

常见岗位:机器学习算法(泛)

答案要点

  1. dp[i][j]:s 前 i 个字符与 p 前 j 个字符是否匹配,dp[0][0] = true
  2. 初始化:dp[0][j] 仅当 p 前 j 个全为 * 时为真
  3. 转移:? 或字符相等取 dp[i-1][j-1];* 取 dp[i][j-1](匹配空)或 dp[i-1][j](多匹配一个)
  4. 复杂度 O(mn),滚动数组可降为 O(n) 空间;连续 * 可合并
  5. 贪心双指针:记录最近的 * 位置,失配时回退让 * 多匹配一个字符

易错点

面试官常见追问

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

相关面试题