题干与适用场景
给定字符串 source 和 target，返回把 source 转换成 target 所需的最少编辑次数。一次编辑可以 插入一个字符、删除一个字符或替换一个字符，每种操作的代价都是一。任一字符串都可能为空，且两者 只含小写英文字母。
source = "horse"
target = "ros"
horse -> rorse 把 h 替换为 r
rorse -> rose 删除 r
rose -> ros 删除 e
答案 = 3设 m = source.length、n = target.length，两个长度都不超过 2,000。题目只要求最小代价，不要求 返回编辑步骤。Wagner–Fischer 论文把字符串校正定义为插入、删除和替换组成的最小代价序列，并给出 时间与两个字符串长度乘积成正比的算法。2026 年的公开面试指南仍把编辑距离作为双字符串动态规划的 典型练习。这些资料能说明本题当前的备考价值，但不能证明特定公司的出题频率或归属。
编辑距离可用于拼写检查、模糊匹配、记录关联和序列比较，不过生产定义可能加入操作权重、字符交换、 归一化或领域专用 token。面试版本刻意限定为单位代价的字符编辑，让状态和证明都有明确边界。
面试官考察点
第一项信号是能给出边界准确的状态定义。令 dp[i][j] 表示把 source 的前 i 个字符变成 target 的前 j 个字符所需的最少编辑次数。只说“i 和 j 之前的答案”过于含糊，无法证明 转移，也无法初始化空前缀。
第二项信号是能推导末尾字符不同时的三种转移。一个最优方案的最后一步只能是删除、插入或替换； 去掉这最后一步后，剩下的正是一个更小的前缀问题。候选人应把每种操作映射到正确的相邻单元格， 而不是死记三个坐标。
第三项信号是末尾字符相同时不凭空增加操作。若 source[i - 1] 等于 target[j - 1]，最优方案可 保留这个字符，值来自 dp[i - 1][j - 1]。证明还要说明这样做不会漏掉更便宜的方案。
第四项信号是看清依赖形状。一行只依赖上一行和本行左侧单元格；只返回距离时，无须保存完整的 O(mn) 矩阵。让较短字符串充当列，就能把额外空间降为 O(min(m, n))。
最后一项信号是始终遵守题目契约。这里插入和删除都是单位代价，距离具有对称性，因此可以交换行列 字符串；若插入和删除权重不同，就不能默认交换。Unicode 文本还必须明确比较单位究竟是 UTF-16 码元、Unicode 码点，还是用户看到的字素簇。
回答前需要澄清的问题
- 允许哪些操作？ 本题允许插入、删除和替换，相邻字符交换不算一次操作。
- 每次编辑代价是多少？ 三种操作代价都为一。加权代价会改变递推式，也可能让距离失去对称性。
- 比较单位是什么？ 题目只有小写英文字母，所以当前 JavaScript 实现可安全使用索引。一般
Unicode 文本需要另行约定。
- 只返回距离还是返回编辑步骤？ 只返回距离。重建操作通常要保留完整表格或显式前驱信息。
- 输入可以为空吗？ 可以。空串变成长度为
j的前缀恰好需要j次插入，反向则需要i
次删除。
- 输入规模多大？ 长度不超过 2,000，
O(mn)时间可接受，但指数递归和不必要的完整矩阵内存
不合适。
- 能否交换两个输入以节省内存？ 在当前单位代价契约下可以，因为距离对称；使用前要先说出
这个前提。
30 秒回答框架
“我定义 dp[i][j] 为源字符串前 i 个字符到目标字符串前 j 个字符的最少编辑次数。空前缀 代价初始化第一行和第一列。末尾字符相等时原样取左上角；不相等时，最后一步只能是删除、插入或 替换，所以取上方、左侧和左上角的最小值再加一。每个单元格只依赖上一行及本行左侧，因此把短串 放在列上，只保存两行。时间是 O(mn)，空间是 O(min(m, n))。我会覆盖空串、相同字符串、 长度不对称情况，并在小输入上与完整矩阵实现对拍。”
分步骤深入解答
从前缀开始定义。令 dp[i][j] 表示把 source[0..i - 1] 转换为 target[0..j - 1] 所需的 最少允许操作数。
空前缀边界直接来自题目契约：
dp[0][j] = j // 插入目标的全部 j 个字符
dp[i][0] = i // 删除源串的全部 i 个字符对两个非空前缀，观察它们的末尾字符。若末尾相同，保留这个共同字符，问题缩小为两个更短的前缀：
如果 source[i - 1] == target[j - 1]：
dp[i][j] = dp[i - 1][j - 1]若末尾不同，对任意最优操作序列的最后一次编辑分类：
删除 source[i - 1]： dp[i - 1][j] + 1
插入 target[j - 1]： dp[i][j - 1] + 1
替换末尾字符： dp[i - 1][j - 1] + 1
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])三种情况完备，因为最后一步必然是题目允许的三种操作之一；它们也都可构造：在所选小前缀的最优 方案后追加对应编辑，就能得到 (i, j) 的合法方案。反过来，从任意最优方案中移除最后一步，剩余 部分就在解决对应的小前缀，代价不可能低于那个单元格。因此字符不同时的递推式成立。
末尾字符相同时，至少存在一个最优方案让它们直接匹配。若某个最优序列仍编辑了源串或目标串的末尾， 可以移除这些末尾影响，改为对齐两个相同字符，代价不会上升；剩余工作正是左上角前缀问题。以空前缀 为基础，对 i + j 做归纳，就能证明每个单元格以及最终的 dp[m][n] 都正确。
填一行时只需要三个旧值：删除对应 previous[j]，插入对应 current[j - 1]，替换或匹配对应 previous[j - 1]。代码让短串作为列。这是在当前对称单位代价定义下的内存优化，不会改变答案。
export function editDistance(source: string, target: string): number {
const rows = source.length >= target.length ? source : target
const columns = source.length >= target.length ? target : source
let previous = Array.from(
{ length: columns.length + 1 },
(_, index) => index,
)
for (let row = 1; row <= rows.length; row += 1) {
const current = new Array<number>(columns.length + 1)
current[0] = row
for (let column = 1; column <= columns.length; column += 1) {
if (rows[row - 1] === columns[column - 1]) {
current[column] = previous[column - 1]
continue
}
const deleteCost = previous[column] + 1
const insertCost = current[column - 1] + 1
const replaceCost = previous[column - 1] + 1
current[column] = Math.min(deleteCost, insertCost, replaceCost)
}
previous = current
}
return previous[columns.length]
}对 source = "horse"、target = "ros"，较短的列维度长度为三，最后一行的末项是三，与一次替换 加两次删除的操作序列一致。算法只返回代价，不声称这条具体编辑序列是唯一答案。
复杂度、边界与工程取舍
算法在概念上填充 (m + 1)(n + 1) 个状态，因此时间复杂度为 O(mn)。每行有 min(m, n) + 1 个单元格，且同时只保留两行，额外空间为 O(min(m, n))。每轮新建一行不改变 渐进界；若要减少分配压力，可以复用两个数组，算法本身无需变化。
在单位插入、删除和替换下，答案最大为 max(m, n)：先替换前 min(m, n) 个字符，再插入或删除 长度差；答案最小为 |m - n|，因为一次编辑最多只让长度改变一。这两个界可作为测试断言。
对一般 JavaScript 字符串，索引操作的是 UTF-16 码元。字符串迭代会按 Unicode 码点产出值，因而 不会拆开代理对，但仍可能拆开一个字素簇，例如 emoji 与肤色修饰符或零宽连接符序列。生产中的相似度 功能必须先决定编辑作用于码元、码点、归一化后的字素簇、单词还是领域 token，再选择分词方式。静默 归一化也可能改变产品语义，因此它应写进契约，而不是藏在这个 DP 循环里。
若调用方只问距离是否不超过 k，可以先在 |m - n| > k 时直接返回 false，再只计算一条对角带； 当活动带中没有状态还能回到预算内时提前停止。这是另一种输出契约，完整距离实现不应为未提出的需求 擅自增加这层复杂度。
高质量示范回答
“我会把问题建模在两个字符串的前缀上。令 dp[i][j] 表示把源字符串前 i 个字符变成目标字符串 前 j 个字符的最小代价，空前缀边界就是对应长度。两个末尾字符相等时沿用左上角；不相等时，按最优 序列的最后一次编辑分类：删除来自上方，插入来自左侧，替换来自左上角，再给三者最小值加一。这三类 覆盖所有允许操作；反向移除最后一步，也能证明递推式没有低估答案。
“每个状态只需要上一行与本行左侧，所以我保存两行。单位插入和删除让距离对称，可以把短串放在列上， 把内存降到 O(min(m, n))，时间仍为 O(mn)；非对称权重下不能这样交换。我会测试两个方向的 空串、相同字符串、horse 到 ros，并用短字符串把结果与完整矩阵实现对拍。若面试官要求编辑步骤， 我会保留前驱信息，不会承诺从已经覆盖的滚动数组中重建。”
常见错误
- 贪心匹配字符 → 重复字符和后续位移会让局部方便的编辑错过全局最小值 → **定义最优前缀状态，
比较所有合法的末步操作。**
- 把第一行和第一列都初始化为零 → 空串转换变成免费 → 边界代价设为对应前缀长度。
- 混淆插入和删除的邻居 → 代码可能通过对称样例，却在不对称前缀上出错 → **说明移除最后一步后
剩下哪个字符串。**
- 末尾字符相等时仍加一 → 没有变化的相同字符被误算成替换 → 相等时原样复制左上角。
- 用滚动数组却承诺返回编辑脚本 → 被覆盖的前驱无法重建路径 → **需要操作序列时保留矩阵或
前驱。**
- 在非对称权重下交换字符串 → 一个方向的插入会变成另一个方向的删除 → **除非代价模型对称，
否则保持原方向。**
- 把 JavaScript 索引称为任意 Unicode 的“字符” → 代理对或字素簇会被意外计数 → **显式定义
并切分比较单位。**
一组聚焦测试包括 ("", "") = 0、("", "abc") = 3、("abc", "") = 3、 ("same", "same") = 0、("aaaa", "aa") = 2、("horse", "ros") = 3 和 ("intention", "execution") = 5。可在小字母表的所有短字符串上，把滚动数组实现与完整矩阵参考 实现对拍；还要检查同一性、当前代价模型下的对称性、|m - n| ≤ d ≤ max(m, n)，以及生成字符串 三元组上的三角不等式。最后用长度为 2,000 的完全相同和完全不同输入跑极限路径，确认实际表现符合 平方时间、线性空间的预期。
面试追问
追问 1：如何返回实际的编辑操作？
保留完整矩阵，再从 (m, n) 反向走。字符相等时不输出操作并走左上角；否则选择一个满足“邻居值加 对应操作代价等于当前值”的单元格。多个最短脚本可能同时存在，因此要定义稳定的平局规则。直接方法 使用 O(mn) 空间。也能用分治方法实现线性空间重建，但那是另一套算法，只有内存要求明确提出时才 值得加入。
追问 2：不同操作有不同权重时怎么改？
每条转移加上对应权重，而不是统一加一。只要代价非负且契约明确，同样的最优子结构证明仍成立。若 插入和删除权重不同，距离可能有方向性，不能再自动交换字符串来缩短行。负编辑代价会破坏通常的距离 含义，需要重新审视模型。
追问 3：如何支持相邻字符交换？
先澄清交换是否仅限相邻字符，以及是否允许相互重叠的交换。受限的 optimal string alignment 递推 可以额外检查前两个字符和左上两行两列的状态；完整 Damerau–Levenshtein 距离则需要不同的状态信息。 只随手加一个对角判断，很可能实现成错误变体。
追问 4：它与最长公共子序列有什么关系？
若禁止替换，或替换代价等于一次删除加一次插入，则只含插入与删除的距离可由 m + n - 2 * LCS(source, target) 得到。单位代价替换下，这个公式通常不等于编辑距离：替换一个 不同字符只要一次，而删除再插入要两次。使用这个关系前必须先说明操作代价。
追问 5：只判断“距离是否不超过 k”时如何加速？
长度差超过 k 时立即返回 false；否则只计算主对角线两侧预算允许的状态，把带外单元格视为不可达， 并在活动前沿已经无法回到预算内时停止。当 k 很小时，这会显著减少工作；不限制距离时的最坏情况 仍是平方级。
追问 6：真实用户可见的 Unicode 文本怎么处理？
先与产品负责人确定比较单位。按码点迭代不会拆开代理对，却仍会拆开部分用户眼中的单个字符。字素分割 更接近可见字符，Unicode 归一化能让规范等价的序列一致比较。语言区域、大小写折叠、重音和 token 规则都是产品决策。先完成这层预处理，再运行 DP，并用支持语言中的真实样例验证。
追问 7：能否把两行再压成一行？
可以。在覆盖 dp[j] 前，先把旧值保存为下一次使用的左上角；此时 dp[j] 仍表示上方单元格， dp[j - 1] 已表示本行左侧单元格。这样只减少常数，不改变渐进空间。面试中两行版本通常更易证明、 也更不容易写错，除非面试官明确要求原地版本。