面试题库 › 算法 / 大模型 › 编辑距离的动态规划解法

编辑距离的动态规划解法

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

哪些公司问过

腾讯3字节跳动2蔚来1英伟达1美团1快手1华为1微软13601拓竹科技1

常见岗位:大模型算法、NLP / 语音、AI 应用 / Agent 开发、机器学习算法(泛)、推理部署与加速

答案要点

  1. 编辑距离:插入、删除、替换三种操作把一个字符串变成另一个的最少次数
  2. dp[i][j]:s1 前 i 个字符变成 s2 前 j 个字符的最小操作数
  3. 边界:dp[i][0] = i,dp[0][j] = j
  4. 字符相等:dp[i][j] = dp[i-1][j-1];否则取 dp[i-1][j](删)、dp[i][j-1](插)、dp[i-1][j-1](换)的最小值加一
  5. 时间 O(mn),空间可用滚动数组优化到 O(n);CER = 编辑距离 / 参考文本长度

易错点

面试官常见追问

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

相关面试题