题目重点：插入、删除、替换均为单位成本，推导三项转移，区分字符交换，并用编辑图最短路核验。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练字符串a变为b，允许单字符插入、删除、替换，成本各1；相同字符保持成本0。
- 不允许把相邻字符交换作为一步，不涉及整词编辑或不同权重。
- 按Unicode code point，空串合法；只返回最少成本，不返回操作序列。
解题路线
- 定义dp[i][j]为a前i字符变成b前j字符的最少操作数，状态是前缀长度而不是当前下标。边界dp[i][0]=i（全部删），dp[0][j]=j（全部插）。
- 考虑最后一步：删掉a第i字符取dp[i−1][j]+1；在a末尾插入b第j字符取dp[i][j−1]+1；对齐末字符取dp[i−1][j−1]+(a[i−1]≠b[j−1])。三个合法来源取最小。
- 为何覆盖最优：编辑可对应两字符串的对齐路径，末端要么只消费a、只消费b、同时消费两者；这三种就是删除、插入、匹配/替换。单位非负成本无需重复修改同一对齐位置来变得更优。
- 每行只依赖上一行和本行左项，所以previous与current两行足够。循环从左向右写current，先初始化current[0]=i；不要把尚未计算的current[j]当作上一行值。
- 交换a、b让b为短串，可将工作内存压到O(min(m,n))。这依赖本文插入与删除等成本、距离对称；若两者权重不同，交换后必须同时交换对应操作权重。
- 只保存两行无法直接从终点回溯操作。要返回一种最短脚本，可保存完整DP与前驱，或使用分治重建以较低空间换额外推导；多个同成本脚本的选择政策也要定义。
- 不能套最长公共子序列公式m+n−2LCS，它对应只允许插删；允许替换时a→b可以一步而非删插两步。交换ab→ba本题是2，不是允许转置操作的距离1。
- 独立验证把短字符串看作图节点，一次合法编辑为单位边，用BFS求最短路；不复用三项DP转移。再单测空串、相等串与Unicode，说明字符合同。
手动走一遍
horse→ros最少3步，可替h为r得到rorse，删除第三位r得到rose，再删除e。a→b只需替换1；ab→ba需2。空串→abc为3；🙂好→🙂你为1。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def edit_distance(a, b):
if len(a) < len(b):
a, b = b, a
previous = list(range(len(b) + 1))
for i, x in enumerate(a, 1):
current = [i] + [0] * len(b)
for j, y in enumerate(b, 1):
current[j] = min(previous[j] + 1, current[j - 1] + 1,
previous[j - 1] + (x != y))
previous = current
return previous[-1]
复杂度
O(mn+m+n)时间（含边界，非空时通常写O(mn)），O(min(m,n)+1)工作空间。全表重建操作需O(mn)空间，操作输出最长O(m+n)。
易错点与追问
容易失分的边界
- 把前缀长度与字符下标混用。
- 漏初始化空前缀。
- LCS插删公式套到允许替换题。
- 两行DP却声称可以直接回溯完整路径。
继续深挖
- 操作权重不同如何调整边界和转移？
- 最大允许距离K可怎样剪枝或做带状DP？
- 允许相邻交换需要额外哪项状态？
- 怎样用分治在低空间重建编辑脚本？
