01先把问题说具体
把 'cat' 改成 'cut',允许每次插入、删除或替换一个字符,求最少操作数。
02一步步得到方法
定义变换方向
dp[i][j] 表示把 a 的前 i 个字符变为 b 的前 j 个字符的最小成本。a 为空时需要插入 j 次;b 为空时需要删除 i 次,因此首行首列分别是 0..m、0..n。
若末尾相等,可以直接保留,代价来自左上。若不等,最后一步可能是删除 a 的末尾,对应 dp[i−1][j]+1;插入 b 的末尾,对应 dp[i][j−1]+1;替换,对应 dp[i−1][j−1]+1。
不要只比较同一位置的字符
插入和删除会改变后续对齐关系。例如 abc→zabc 只需一次插入,而逐位置比较会误认为很多字符都不同。二维状态正是保存不同前缀对齐的方式。
本课单位代价 Levenshtein 距离不包含相邻交换。若题目允许交换,需新增合法操作及依赖,不能声称当前代码已经覆盖。
三个操作对应三个前缀状态
从短前缀到长前缀,删除消耗源字符,插入消耗目标字符,替换同时消耗两边字符。因此三个邻居分别代表不同的剩余编辑任务,不是任意挑三个方向。
若字符相同可零成本对齐,若不同再加替换成本。操作权重不同时公式要显式使用各权重;相邻交换也不是普通 Levenshtein 距离已有的操作,需要扩展模型。
03把一个小例子完全算清楚
a='cat',b='cut'。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 空行 | [0,1,2,3] | 逐个插入目标前缀 |
| c 行 | [1,0,1,2] | c 与 c 可保留 |
| ca 行 | [2,1,1,2] | a→u 替换一次 |
| cat 行 | [3,2,2,1] | 最后 t 保留 |
窄屏可左右滑动表格,阅读完整计算与理由。
距离为 1;表格同时比较不同长度的前缀,自动寻找最佳对齐。
04为什么这个方法成立
- 空前缀边界是唯一必要的插入或删除数量。
- 任一最优编辑序列的最后一步属于保留、插入、删除、替换之一。
- 相应更短前缀若不是最优,可替换为更优方案,故取候选最小值正确。
05把推导翻译成代码
Python · 可独立运行的教学实现
def edit_distance(a,b):
dp = [[0]*(len(b)+1) for _ in range(len(a)+1)]
for i in range(len(a)+1): dp[i][0] = i
for j in range(len(b)+1): dp[0][j] = j
for i in range(1,len(a)+1):
for j in range(1,len(b)+1):
replace = dp[i-1][j-1] + (a[i-1] != b[j-1])
dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,replace)
return dp[-1][-1]逐个理解关键决定
(a[i-1] != b[j-1])- 相等时代价 0,不相等时代价 1,统一保留与替换。
dp[i][0] = i- 不能把整表边界都初始化为零,否则删除成本被忽略。
06时间、空间与实现范围
时间 O(nm),完整表空间 O(nm);只求距离可保存两行。
文本按 Python 码点处理,用户可见字符层面的编辑距离需要先做字素簇分段。
07改变条件,检查哪里会出错
把 LCS 公式直接当作包含替换的距离
cat→cut 可替换一次,删除再插入要两次,两种操作集合不同。
空串边界全部设为0
空串变为长度 j 的目标需 j 次插入,反向需 i 次删除,边界必须表达这些真实成本。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
空串到 'abc' 距离多少?
需要一点提示
只能插入。
查看解析与答案
3。
'ab'→'ba' 本课距离多少?
需要一点提示
没有交换操作。
查看解析与答案
2,可替换两次;不能按一次相邻交换计算。
删除代价 2、插入 1、替换 3 怎么改?
需要一点提示
同时修改转移与边界。
查看解析与答案
首列 2i、首行 j,三条候选分别加 2、1、3,相等保留仍为 0。