LeetCode 补充题 178. 带权编辑距离
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 72. 编辑距离
LeetCode 原题中插入、删除、替换的费用均为 1；本文分别使用参数 ic、dc、rc 指定费用。
:::
给你两个字符串
a和b，返回将a转换成b所需的最小总费用。你可以对
a进行以下操作：
- 插入一个字符，费用为
ic。- 删除一个字符，费用为
dc。- 替换一个字符，费用为
rc。字符相同时可以保留原字符，费用为
0。
示例 1：
输入：
a = "abc", b = "adc", ic = 5, dc = 3, rc = 2
输出：2
解释： 将字符串a中的第二个字符b替换为d，花费 2，得到字符串"adc"。
示例 2：
输入：
a = "", b = "ab", ic = 5, dc = 3, rc = 2
输出：10
解释： 插入a、b两个字符，每次花费 5。
提示：
-
a、b均包含0到5000个 Unicode 码点，允许空串。 -
0 <= ic, dc, rc <= 10000。 - 字符按 Unicode 码点比较，结果使用 64 位整数。
题意分析
需要将源串前缀逐步变为目标串前缀，每个前缀对可能由多种编辑过程到达，只保留费用最小者即可。插入、删除、替换费用不同，不能再把每步都按 1 计算。
以最后一次操作分类，可得到删除源末字符、插入目标末字符、对齐两端字符三类转移。空前缀同样需要按实际费用初始化；插入与删除费用不同时，也不能随意交换两串来节省空间而保持费用不变。
解法：带独立操作费用的滚动编辑距离
核心思路
[!blue]
面试先用二维状态讲清楚，再解释为什么能只保留一行。设
F(i,j)表示把a的前i个码点变成b的前j个码点的最小费用。最后一步只有三类：删除
a的末字符，来自F(i-1,j) + dc；插入b的末字符，来自F(i,j-1) + ic；保留或替换末字符，来自F(i-1,j-1) + cost，相等时cost = 0，否则为rc。三者取最小值。空串边界为F(0,j)=j*ic、F(i,0)=i*dc。滚动更新到第
i行第j列时：old = dp[j]仍是上一行同列，dp[j-1]已是本行左侧，diagonal保存上一行左上角。先用这三个旧含义计算新dp[j]，再令diagonal = old，供下一列使用。例如
a = "a"、b = "b"，若替换费用为 10，删除和插入各为 2，递推会选择总费用 4 的删加插，不会因为有“替换”操作就固定优先替换。
解题步骤
- 初始化
dp[j] = j * ic，表示空串变成目标前缀的插入费用。- 开始新一行前把旧
dp[0]存入diagonal，再写入当前空目标前缀的删除费用i * dc。- 逐列先保存
old = dp[j]，比较删、插、保留或替换的费用后覆盖该格，再令diagonal = old。- 返回最后一列的费用；码点数组和滚动数组分别承担字符访问与状态保存。
代码实现
class Solution {
public long editCost(String a, String b, int ic, int dc, int rc) {
int[] x = a.codePoints().toArray();
int[] y = b.codePoints().toArray();
long[] dp = new long[y.length + 1];
for (int j = 1; j <= y.length; j++) {
dp[j] = (long) j * ic;
}
for (int i = 1; i <= x.length; i++) {
long diagonal = dp[0];
dp[0] = (long) i * dc;
for (int j = 1; j <= y.length; j++) {
long old = dp[j];
long replace = diagonal + (x[i - 1] == y[j - 1] ? 0 : rc);
dp[j] = Math.min(replace, Math.min(old + dc, dp[j - 1] + ic));
diagonal = old;
}
}
return dp[y.length];
}
}
func editCost(a, b string, ic, dc, rc int64) int64 {
x, y := []rune(a), []rune(b)
dp := make([]int64, len(y)+1)
for j := 1; j <= len(y); j++ {
dp[j] = int64(j) * ic
}
for i := 1; i <= len(x); i++ {
diagonal := dp[0]
dp[0] = int64(i) * dc
for j := 1; j <= len(y); j++ {
old := dp[j]
cost := rc
if x[i-1] == y[j-1] {
cost = 0
}
dp[j] = min(diagonal+cost, min(old+dc, dp[j-1]+ic))
diagonal = old
}
}
return dp[len(y)]
}
复杂度分析
- 时间复杂度：$O(mn)$。
- 空间复杂度：$O(m+n)$，包含字符数组；滚动DP本身占O(n)。
关键点总结
[!green]
滚动数组更新前保存旧值，避免覆盖左上角；替换比先删除再插入更贵时，递推会自然选择后者。
易错点总结
[!yellow]
初始化也要乘费用，不能统一加1。Java和Go均按Unicode码点比较，避免UTF-8多字节拆分造成费用差异。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 72. 编辑距离 | 中等 | 复用前缀编辑距离状态，插入、删除、替换分别加各自费用，初始化也要按费用计算。 |
| 583. 两个字符串的删除操作 | 中等 | 当替换不优于删除加插入时，可以对照保留公共子序列后的删插代价，不能固定优先替换。 |