14.6 编辑距离问题¶
编辑距离,也称 Levenshtein 距离,指两个字符串之间互相转换的最少修改次数,通常用于在信息检索和自然语言处理中度量两个序列的相似度。
Question
输入两个字符串 \(s\) 和 \(t\) ,返回将 \(s\) 转换为 \(t\) 所需的最少编辑步数。
你可以在一个字符串中进行三种编辑操作:插入一个字符、删除一个字符、将字符替换为任意一个字符。
如图 14-27 所示,将 kitten 转换为 sitting 需要编辑 3 步,包括 2 次替换操作与 1 次添加操作;将 hello 转换为 algo 需要 3 步,包括 2 次替换操作和 1 次删除操作。
图 14-27 编辑距离的示例数据
图解 14-27:编辑距离:两个三步转换示例
并列展示 kitten 转为 sitting、hello 转为 algo 的字符对应关系,两组示例的最少编辑步数均为 3。
每次编辑允许插入(添加)、删除或替换一个字符。
画面左右并列展示两组字符逐位对齐图;每组自上而下为源串行、编辑后的中间过渡行、目标串行。两组的箭头都表示字符位置的编辑类型与对应关系,不规定三次编辑的唯一先后顺序。
左图将源字符串 s = kitten 转换为目标字符串 t = sitting:首字母 k 替换为 s(蓝色),第 5 个字母 e 替换为 i(蓝色),并在末尾添加字母 g(紫色);其余未修改的 4 个字母 i、t、t、n 原样保留,中间过渡行与目标行以竖直虚线对齐。中间过渡行依次为 s、i、t、t、i、n、g,其中替换得到的 s、i 为蓝色,新增的 g 为紫色;该行的字符已与目标串相同。按字符计数,长度由 6 变为 7。
右图将源字符串 s = hello 转换为目标字符串 t = algo:首字母 h 被删除(在中间过渡行以淡橙色虚化显示 h,不再向下进入目标串),第 2 个字母 e 替换为 a(蓝色),两个连续 l 中的后一个 l 替换为 g(蓝色),而前一个 l 与末尾 o 原样保留,中间过渡行与目标行以竖直虚线对齐。中间过渡行保留虚化的 h,后面依次为 a、l、g、o;目标行只保留 a、l、g、o。按字符计数,长度由 5 变为 4。
| 起点 | 终点 | 替换 | 插入或删除 | 步数 |
|---|---|---|---|---|
| kitten | sitting | k→s;e→i | 末尾插入g | 3 |
| hello | algo | e→a;后一个l→g | 删除开头h | 3 |
图中未直接标出总步数;表中步数 3 由每组两次替换加一次插入或删除相加得到,也达到正文给出的最少编辑次数。
编辑距离问题可以很自然地用决策树模型来解释。字符串对应树节点,一轮决策(一次编辑操作)对应树的一条边。
如图 14-28 所示,在不限制操作的情况下,每个节点都可以派生出许多条边,每条边对应一种操作,这意味着从 hello 转换到 algo 有许多种可能的路径。
从决策树的角度看,本题的目标是求解节点 hello 和节点 algo 之间的最短路径。
图 14-28 基于决策树模型表示编辑距离问题
图解 14-28:编辑距离的决策树
将字符串作为节点、单次编辑作为有向边,在决策树中寻找从 hello 到 algo 的最短路径;图中展示一条三步转换路径,其他分支未展开。
在决策树模型下,每个节点代表一个字符串状态,从节点发出的每条有向边代表一轮决策(一次插入、删除或替换操作)。求解字符串 s = hello 到 t = algo 的编辑距离,等价于在这棵决策树中寻找从根节点 hello 到目标节点 algo 的最短路径。
画面自上而下展开左侧一条含 4 个字符串节点、3 条有向边的路径,顶层为 s = hello,底层为 t = algo。下表依次列出各条边及操作;图中第一条边只写“将 l 替换为 g”,“后一个 l”是对照两个节点字符串后补充的定位说明。
在前三层的每个展开节点(hello、helgo、halgo)右侧,还各画出 3 条指向省略号“…”的分支箭头,表示在不限制操作的情况下每个字符串都可以派生出许多其他编辑选择;这些省略分支并未写出具体字符串,本图旨在直观说明决策树最短路径视角,而非穷举整棵搜索树。
| 起点字符串 | 操作 | 得到的字符串 |
|---|---|---|
| hello | 将后一个 l 替换为 g | helgo |
| helgo | 将 e 替换为 a | halgo |
| halgo | 删除开头的 h | algo |
这条路径用 3 次编辑从 hello 到达 algo,达到本节图 14-27 例题给出的编辑距离 3。单看这一条展开路径,只能确认 3 次编辑可行,不能据此排除更短路径。
1. 动态规划思路¶
第一步:思考每轮的决策,定义状态,从而得到 \(dp\) 表
每一轮的决策是对字符串 \(s\) 进行一次编辑操作。
我们希望在编辑操作的过程中,问题的规模逐渐缩小,这样才能构建子问题。设字符串 \(s\) 和 \(t\) 的长度分别为 \(n\) 和 \(m\) ,我们先考虑两字符串尾部的字符 \(s[n-1]\) 和 \(t[m-1]\) 。
- 若 \(s[n-1]\) 和 \(t[m-1]\) 相同,我们可以跳过它们,直接考虑 \(s[n-2]\) 和 \(t[m-2]\) 。
- 若 \(s[n-1]\) 和 \(t[m-1]\) 不同,我们需要对 \(s\) 进行一次编辑(插入、删除、替换),使得两字符串尾部的字符相同,从而可以跳过它们,考虑规模更小的问题。
也就是说,我们在字符串 \(s\) 中进行的每一轮决策(编辑操作),都会使得 \(s\) 和 \(t\) 中剩余的待匹配字符发生变化。因此,状态为当前在 \(s\) 和 \(t\) 中考虑的第 \(i\) 和第 \(j\) 个字符,记为 \([i, j]\) 。
状态 \([i, j]\) 对应的子问题:将 \(s\) 的前 \(i\) 个字符更改为 \(t\) 的前 \(j\) 个字符所需的最少编辑步数。
至此,得到一个尺寸为 \((n+1) \times (m+1)\) 的二维 \(dp\) 表。
第二步:找出最优子结构,进而推导出状态转移方程
考虑子问题 \(dp[i, j]\) ,其对应的两个字符串的尾部字符为 \(s[i-1]\) 和 \(t[j-1]\) ,可根据不同编辑操作分为图 14-29 所示的三种情况。
- 在 \(s[i-1]\) 之后添加 \(t[j-1]\) ,则剩余子问题 \(dp[i, j-1]\) 。
- 删除 \(s[i-1]\) ,则剩余子问题 \(dp[i-1, j]\) 。
- 将 \(s[i-1]\) 替换为 \(t[j-1]\) ,则剩余子问题 \(dp[i-1, j-1]\) 。
图 14-29 编辑距离的状态转移
图解 14-29:编辑距离的状态转移
以将 book 转换为 code 为例,展示尾字符 k 与 e 不同时,通过添加、删除、替换分解出的三条剩余前缀子问题。
记状态 dp[i, j] 表示将源字符串 s 的前 i 个字符转换为目标字符串 t 的前 j 个字符所需的最少编辑步数,每次添加、删除或替换操作的代价均为 1。本图以 s = book、t = code(当前前缀长度 i = 4、j = 4)为例,剖析两字符串当前尾部字符 s[i-1] = k 与 t[j-1] = e 不相同时的状态转移来源。
左侧为当前状态 dp[i, j],右侧自上而下为插入(添加)、删除、替换三条支路。灰化的尾字符表示已匹配或已删除,不再属于待处理的剩余前缀。
插入后,新增的尾字符与目标尾字符匹配抵消,原源串未消耗字符,因此仅 j 减 1。删除时只去掉源串尾字符,因此仅 i 减 1。替换后两串尾字符匹配抵消,因此 i 与 j 同时减 1。
下表按三条支路的顺序区分“操作后的源串”与“剩余源前缀”,并列出对应子状态;本图未计算 book 到 code 的最终编辑距离。
| 操作 | 操作后的源串 | 剩余源前缀 | 剩余目标前缀 | 子状态 |
|---|---|---|---|---|
| 插入 e | booke | book | cod | dp[i,j-1] |
| 删除 k | boo | boo | code | dp[i-1,j] |
| 替换 k 为 e | booe | boo | cod | dp[i-1,j-1] |
三种操作各付出 1 步,选择剩余子问题所需步数最少的一种,因此尾字符不同时有 dp[i,j] = min(dp[i,j-1], dp[i-1,j], dp[i-1,j-1]) + 1。
根据以上分析,可得最优子结构:\(dp[i, j]\) 的最少编辑步数等于 \(dp[i, j-1]\)、\(dp[i-1, j]\)、\(dp[i-1, j-1]\) 三者中的最少编辑步数,再加上本次的编辑步数 \(1\) 。对应的状态转移方程为:
请注意,当 \(s[i-1]\) 和 \(t[j-1]\) 相同时,无须编辑当前字符,这种情况下的状态转移方程为:
第三步:确定边界条件和状态转移顺序
当两字符串都为空时,编辑步数为 \(0\) ,即 \(dp[0, 0] = 0\) 。当 \(s\) 为空但 \(t\) 不为空时,最少编辑步数等于 \(t\) 的长度,即首行 \(dp[0, j] = j\) 。当 \(s\) 不为空但 \(t\) 为空时,最少编辑步数等于 \(s\) 的长度,即首列 \(dp[i, 0] = i\) 。
观察状态转移方程,解 \(dp[i, j]\) 依赖左方、上方、左上方的解,因此通过两层循环正序遍历整个 \(dp\) 表即可。
2. 代码实现¶
def edit_distance_dp(s: str, t: str) -> int:
"""编辑距离:动态规划"""
n, m = len(s), len(t)
dp = [[0] * (m + 1) for _ in range(n + 1)]
# 状态转移:首行首列
for i in range(1, n + 1):
dp[i][0] = i
for j in range(1, m + 1):
dp[0][j] = j
# 状态转移:其余行和列
for i in range(1, n + 1):
for j in range(1, m + 1):
if s[i - 1] == t[j - 1]:
# 若两字符相等,则直接跳过此两字符
dp[i][j] = dp[i - 1][j - 1]
else:
# 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
return dp[n][m]
/* 编辑距离:动态规划 */
int editDistanceDP(string s, string t) {
int n = s.length(), m = t.length();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
// 状态转移:首行首列
for (int i = 1; i <= n; i++) {
dp[i][0] = i;
}
for (int j = 1; j <= m; j++) {
dp[0][j] = j;
}
// 状态转移:其余行和列
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i - 1] == t[j - 1]) {
// 若两字符相等,则直接跳过此两字符
dp[i][j] = dp[i - 1][j - 1];
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
}
}
}
return dp[n][m];
}
/* 编辑距离:动态规划 */
int editDistanceDP(String s, String t) {
int n = s.length(), m = t.length();
int[][] dp = new int[n + 1][m + 1];
// 状态转移:首行首列
for (int i = 1; i <= n; i++) {
dp[i][0] = i;
}
for (int j = 1; j <= m; j++) {
dp[0][j] = j;
}
// 状态转移:其余行和列
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
// 若两字符相等,则直接跳过此两字符
dp[i][j] = dp[i - 1][j - 1];
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
}
}
}
return dp[n][m];
}
/* 编辑距离:动态规划 */
int EditDistanceDP(string s, string t) {
int n = s.Length, m = t.Length;
int[,] dp = new int[n + 1, m + 1];
// 状态转移:首行首列
for (int i = 1; i <= n; i++) {
dp[i, 0] = i;
}
for (int j = 1; j <= m; j++) {
dp[0, j] = j;
}
// 状态转移:其余行和列
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i - 1] == t[j - 1]) {
// 若两字符相等,则直接跳过此两字符
dp[i, j] = dp[i - 1, j - 1];
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[i, j] = Math.Min(Math.Min(dp[i, j - 1], dp[i - 1, j]), dp[i - 1, j - 1]) + 1;
}
}
}
return dp[n, m];
}
/* 编辑距离:动态规划 */
func editDistanceDP(s string, t string) int {
n := len(s)
m := len(t)
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, m+1)
}
// 状态转移:首行首列
for i := 1; i <= n; i++ {
dp[i][0] = i
}
for j := 1; j <= m; j++ {
dp[0][j] = j
}
// 状态转移:其余行和列
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
if s[i-1] == t[j-1] {
// 若两字符相等,则直接跳过此两字符
dp[i][j] = dp[i-1][j-1]
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[i][j] = MinInt(MinInt(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1
}
}
}
return dp[n][m]
}
/* 编辑距离:动态规划 */
func editDistanceDP(s: String, t: String) -> Int {
let n = s.utf8CString.count
let m = t.utf8CString.count
var dp = Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1)
// 状态转移:首行首列
for i in 1 ... n {
dp[i][0] = i
}
for j in 1 ... m {
dp[0][j] = j
}
// 状态转移:其余行和列
for i in 1 ... n {
for j in 1 ... m {
if s.utf8CString[i - 1] == t.utf8CString[j - 1] {
// 若两字符相等,则直接跳过此两字符
dp[i][j] = dp[i - 1][j - 1]
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1
}
}
}
return dp[n][m]
}
/* 编辑距离:动态规划 */
function editDistanceDP(s, t) {
const n = s.length,
m = t.length;
const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));
// 状态转移:首行首列
for (let i = 1; i <= n; i++) {
dp[i][0] = i;
}
for (let j = 1; j <= m; j++) {
dp[0][j] = j;
}
// 状态转移:其余行和列
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
if (s.charAt(i - 1) === t.charAt(j - 1)) {
// 若两字符相等,则直接跳过此两字符
dp[i][j] = dp[i - 1][j - 1];
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[i][j] =
Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1;
}
}
}
return dp[n][m];
}
/* 编辑距离:动态规划 */
function editDistanceDP(s: string, t: string): number {
const n = s.length,
m = t.length;
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: m + 1 }, () => 0)
);
// 状态转移:首行首列
for (let i = 1; i <= n; i++) {
dp[i][0] = i;
}
for (let j = 1; j <= m; j++) {
dp[0][j] = j;
}
// 状态转移:其余行和列
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
if (s.charAt(i - 1) === t.charAt(j - 1)) {
// 若两字符相等,则直接跳过此两字符
dp[i][j] = dp[i - 1][j - 1];
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[i][j] =
Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1;
}
}
}
return dp[n][m];
}
/* 编辑距离:动态规划 */
int editDistanceDP(String s, String t) {
int n = s.length, m = t.length;
List<List<int>> dp = List.generate(n + 1, (_) => List.filled(m + 1, 0));
// 状态转移:首行首列
for (int i = 1; i <= n; i++) {
dp[i][0] = i;
}
for (int j = 1; j <= m; j++) {
dp[0][j] = j;
}
// 状态转移:其余行和列
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i - 1] == t[j - 1]) {
// 若两字符相等,则直接跳过此两字符
dp[i][j] = dp[i - 1][j - 1];
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
}
}
}
return dp[n][m];
}
/* 编辑距离:动态规划 */
fn edit_distance_dp(s: &str, t: &str) -> i32 {
let (n, m) = (s.len(), t.len());
let mut dp = vec![vec![0; m + 1]; n + 1];
// 状态转移:首行首列
for i in 1..=n {
dp[i][0] = i as i32;
}
for j in 1..m {
dp[0][j] = j as i32;
}
// 状态转移:其余行和列
for i in 1..=n {
for j in 1..=m {
if s.chars().nth(i - 1) == t.chars().nth(j - 1) {
// 若两字符相等,则直接跳过此两字符
dp[i][j] = dp[i - 1][j - 1];
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[i][j] =
std::cmp::min(std::cmp::min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
}
}
}
dp[n][m]
}
/* 编辑距离:动态规划 */
int editDistanceDP(char *s, char *t, int n, int m) {
int **dp = malloc((n + 1) * sizeof(int *));
for (int i = 0; i <= n; i++) {
dp[i] = calloc(m + 1, sizeof(int));
}
// 状态转移:首行首列
for (int i = 1; i <= n; i++) {
dp[i][0] = i;
}
for (int j = 1; j <= m; j++) {
dp[0][j] = j;
}
// 状态转移:其余行和列
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i - 1] == t[j - 1]) {
// 若两字符相等,则直接跳过此两字符
dp[i][j] = dp[i - 1][j - 1];
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[i][j] = myMin(myMin(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
}
}
}
int res = dp[n][m];
// 释放内存
for (int i = 0; i <= n; i++) {
free(dp[i]);
}
return res;
}
/* 编辑距离:动态规划 */
fun editDistanceDP(s: String, t: String): Int {
val n = s.length
val m = t.length
val dp = Array(n + 1) { IntArray(m + 1) }
// 状态转移:首行首列
for (i in 1..n) {
dp[i][0] = i
}
for (j in 1..m) {
dp[0][j] = j
}
// 状态转移:其余行和列
for (i in 1..n) {
for (j in 1..m) {
if (s[i - 1] == t[j - 1]) {
// 若两字符相等,则直接跳过此两字符
dp[i][j] = dp[i - 1][j - 1]
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1
}
}
}
return dp[n][m]
}
### 编辑距离:动态规划 ###
def edit_distance_dp(s, t)
n, m = s.length, t.length
dp = Array.new(n + 1) { Array.new(m + 1, 0) }
# 状态转移:首行首列
(1...(n + 1)).each { |i| dp[i][0] = i }
(1...(m + 1)).each { |j| dp[0][j] = j }
# 状态转移:其余行和列
for i in 1...(n + 1)
for j in 1...(m +1)
if s[i - 1] == t[j - 1]
# 若两字符相等,则直接跳过此两字符
dp[i][j] = dp[i - 1][j - 1]
else
# 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[i][j] = [dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]].min + 1
end
end
end
dp[n][m]
end
可视化运行
如图 14-30 所示,编辑距离问题的状态转移过程与背包问题非常类似,都可以看作填写一个二维网格的过程。
图 14-30 编辑距离的动态规划过程
图解 14-30:编辑距离的动态规划
按源前缀与目标前缀逐格递推,求将字符串 bag 转换为 pack 的最少编辑步数。
源字符串 s 为 bag(长度 3),目标字符串 t 为 pack(长度 4);注意本图输入与正文其他示例不同。每次可插入、删除或替换一个字符,单次操作成本均为 1。
状态 dp[i, j] 表示将源串 s 的前 i 个字符(源前缀)转换为目标串 t 的前 j 个字符(目标前缀)所需的最少编辑步数。二维表共 4 行 5 列:行 i = 0 至 3 对应源前缀空串、b、ba、bag;列 j = 0 至 4 对应目标前缀空串、p、pa、pac、pack。
先创建 4×5 全零表,其中 dp[0, 0] 已为两空串转换的有效边界 0;再初始化首行正长度格 dp[0, j] = j(空串连续插入 j 个字符变为目标前缀)与首列正长度格 dp[i, 0] = i(源前缀连续删除 i 个字符变为空串)。其余 12 个内部格按行从上到下、每行从左到右依次求解。
求解 dp[i, j] 时比较当前源前缀尾字符 s[i - 1] 与目标前缀尾字符 t[j - 1]:若两尾字符相同,无需新增编辑操作,直接等于左上方 dp[i - 1, j - 1](不加 1);若不同,则比较左方 dp[i, j - 1](插入)、上方 dp[i - 1, j](删除)、左上方 dp[i - 1, j - 1](替换)三者的最小值再加 1。每步保留一张有唯一名称的完整状态表,逐格标明数值及“边界有效”“已计算”或“未计算初值”;第 15 步将右下角标为“返回值”。行列头同时给出 i、j 和对应前缀,可直接按坐标或前缀查询。
创建 4×5 初始全零 dp 表
根据源串 s = bag(长度 3)与目标串 t = pack(长度 4),创建 4×5 的二维 dp 表。当前 20 格数值均为 0,其中 dp[0, 0] 已是空串转空串的有效边界;其余 19 格为未计算初值,首行与首列的正长度边界尚待设置。
编辑距离第 1 步:全零表的完整 dp 表 源前缀 / 目标前缀 j=0,空串 j=1,p j=2,pa j=3,pac j=4,pack i=0,空串 0,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 i=1,b 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 i=2,ba 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 i=3,bag 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 初始化首行与首列空串转换边界
保留空串转空串的 dp[0, 0] = 0。初始化首行 dp[0, 0] 至 dp[0, 4] 为 [0, 1, 2, 3, 4](源前缀为空串,转为长 j 的目标前缀空串、p、pa、pac、pack 需连续插入 j 个字符,其中空串转 pack 为 dp[0, 4] = 4);初始化首列 dp[0, 0] 至 dp[3, 0] 为 [0, 1, 2, 3](长 i 的源前缀空串、b、ba、bag 转为空串需连续删除 i 个字符,其中 bag 转空串为 dp[3, 0] = 3)。内部第 1 至 3 行、第 1 至 4 列的 12 个 0 仍为未计算初值。
编辑距离第 2 步:空串边界初始化后的完整 dp 表 源前缀 / 目标前缀 j=0,空串 j=1,p j=2,pa j=3,pac j=4,pack i=0,空串 0,边界有效 1,边界有效 2,边界有效 3,边界有效 4,边界有效 i=1,b 1,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 i=2,ba 2,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 i=3,bag 3,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[1, 1](源前缀 b 转目标前缀 p):最少 1 步
处理 i = 1, j = 1,求源前缀 b 转为目标前缀 p 的 dp[1, 1]:源尾字符 b 与目标尾字符 p 不同,比较左方 dp[1, 0] = 1、上方 dp[0, 1] = 1、左上方 dp[0, 0] = 0,取最小值 0 加 1(对应将 b 替换为 p),写入 dp[1, 1] = 1。
编辑距离第 3 步:计算 dp[1, 1] 后的完整 dp 表 源前缀 / 目标前缀 j=0,空串 j=1,p j=2,pa j=3,pac j=4,pack i=0,空串 0,边界有效 1,边界有效 2,边界有效 3,边界有效 4,边界有效 i=1,b 1,边界有效 1,已计算 0,未计算初值 0,未计算初值 0,未计算初值 i=2,ba 2,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 i=3,bag 3,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[1, 2](源前缀 b 转目标前缀 pa):最少 2 步
处理 i = 1, j = 2,求源前缀 b 转为目标前缀 pa 的 dp[1, 2]:源尾字符 b 与目标尾字符 a 不同,比较左方 dp[1, 1] = 1、上方 dp[0, 2] = 2、左上方 dp[0, 1] = 1,取最小值 1 加 1,写入 dp[1, 2] = 2。
编辑距离第 4 步:计算 dp[1, 2] 后的完整 dp 表 源前缀 / 目标前缀 j=0,空串 j=1,p j=2,pa j=3,pac j=4,pack i=0,空串 0,边界有效 1,边界有效 2,边界有效 3,边界有效 4,边界有效 i=1,b 1,边界有效 1,已计算 2,已计算 0,未计算初值 0,未计算初值 i=2,ba 2,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 i=3,bag 3,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[1, 3](源前缀 b 转目标前缀 pac):最少 3 步
处理 i = 1, j = 3,求源前缀 b 转为目标前缀 pac 的 dp[1, 3]:源尾字符 b 与目标尾字符 c 不同,比较左方 dp[1, 2] = 2、上方 dp[0, 3] = 3、左上方 dp[0, 2] = 2,取最小值 2 加 1,写入 dp[1, 3] = 3。
编辑距离第 5 步:计算 dp[1, 3] 后的完整 dp 表 源前缀 / 目标前缀 j=0,空串 j=1,p j=2,pa j=3,pac j=4,pack i=0,空串 0,边界有效 1,边界有效 2,边界有效 3,边界有效 4,边界有效 i=1,b 1,边界有效 1,已计算 2,已计算 3,已计算 0,未计算初值 i=2,ba 2,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 i=3,bag 3,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[1, 4](源前缀 b 转目标串 pack):最少 4 步
处理 i = 1, j = 4,求源前缀 b 转为完整目标串 pack 的 dp[1, 4]:源尾字符 b 与目标尾字符 k 不同,比较左方 dp[1, 3] = 3、上方 dp[0, 4] = 4、左上方 dp[0, 3] = 3,取最小值 3 加 1,写入 dp[1, 4] = 4,完成第 1 行。
编辑距离第 6 步:计算 dp[1, 4] 后的完整 dp 表 源前缀 / 目标前缀 j=0,空串 j=1,p j=2,pa j=3,pac j=4,pack i=0,空串 0,边界有效 1,边界有效 2,边界有效 3,边界有效 4,边界有效 i=1,b 1,边界有效 1,已计算 2,已计算 3,已计算 4,已计算 i=2,ba 2,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 i=3,bag 3,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[2, 1](源前缀 ba 转目标前缀 p):最少 2 步
进入第 2 行,处理 i = 2, j = 1,求源前缀 ba 转为目标前缀 p 的 dp[2, 1]:源尾字符 a 与目标尾字符 p 不同,比较左方 dp[2, 0] = 2、上方 dp[1, 1] = 1、左上方 dp[1, 0] = 1,取最小值 1 加 1,写入 dp[2, 1] = 2。
编辑距离第 7 步:计算 dp[2, 1] 后的完整 dp 表 源前缀 / 目标前缀 j=0,空串 j=1,p j=2,pa j=3,pac j=4,pack i=0,空串 0,边界有效 1,边界有效 2,边界有效 3,边界有效 4,边界有效 i=1,b 1,边界有效 1,已计算 2,已计算 3,已计算 4,已计算 i=2,ba 2,边界有效 2,已计算 0,未计算初值 0,未计算初值 0,未计算初值 i=3,bag 3,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[2, 2](源前缀 ba 转目标前缀 pa):尾字符同为 a,直接取 1
处理 i = 2, j = 2,求源前缀 ba 转为目标前缀 pa 的 dp[2, 2]:当前源前缀尾字符 s[1] 与目标前缀尾字符 t[1] 同为 a,两尾字符完全匹配,无需新增编辑操作,因此不在 b 转 p 的结果上加 1,直接复制左上方 dp[1, 1] = 1,写入 dp[2, 2] = 1。
编辑距离第 8 步:计算 dp[2, 2] 后的完整 dp 表 源前缀 / 目标前缀 j=0,空串 j=1,p j=2,pa j=3,pac j=4,pack i=0,空串 0,边界有效 1,边界有效 2,边界有效 3,边界有效 4,边界有效 i=1,b 1,边界有效 1,已计算 2,已计算 3,已计算 4,已计算 i=2,ba 2,边界有效 2,已计算 1,已计算 0,未计算初值 0,未计算初值 i=3,bag 3,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[2, 3](源前缀 ba 转目标前缀 pac):最少 2 步
处理 i = 2, j = 3,求源前缀 ba 转为目标前缀 pac 的 dp[2, 3]:源尾字符 a 与目标尾字符 c 不同,比较左方 dp[2, 2] = 1、上方 dp[1, 3] = 3、左上方 dp[1, 2] = 2,取左方最小值 1(在 ba 转 pa 的 1 步基础上插入 c)加 1,写入 dp[2, 3] = 2。
编辑距离第 9 步:计算 dp[2, 3] 后的完整 dp 表 源前缀 / 目标前缀 j=0,空串 j=1,p j=2,pa j=3,pac j=4,pack i=0,空串 0,边界有效 1,边界有效 2,边界有效 3,边界有效 4,边界有效 i=1,b 1,边界有效 1,已计算 2,已计算 3,已计算 4,已计算 i=2,ba 2,边界有效 2,已计算 1,已计算 2,已计算 0,未计算初值 i=3,bag 3,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[2, 4](源前缀 ba 转目标串 pack):最少 3 步
处理 i = 2, j = 4,求源前缀 ba 转为完整目标串 pack 的 dp[2, 4]:源尾字符 a 与目标尾字符 k 不同,比较左方 dp[2, 3] = 2、上方 dp[1, 4] = 4、左上方 dp[1, 3] = 3,取左方最小值 2 加 1,写入 dp[2, 4] = 3,完成第 2 行。
编辑距离第 10 步:计算 dp[2, 4] 后的完整 dp 表 源前缀 / 目标前缀 j=0,空串 j=1,p j=2,pa j=3,pac j=4,pack i=0,空串 0,边界有效 1,边界有效 2,边界有效 3,边界有效 4,边界有效 i=1,b 1,边界有效 1,已计算 2,已计算 3,已计算 4,已计算 i=2,ba 2,边界有效 2,已计算 1,已计算 2,已计算 3,已计算 i=3,bag 3,边界有效 0,未计算初值 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[3, 1](源串 bag 转目标前缀 p):最少 3 步
进入第 3 行,处理 i = 3, j = 1,求完整源串 bag 转为目标前缀 p 的 dp[3, 1]:源尾字符 g 与目标尾字符 p 不同,比较左方 dp[3, 0] = 3、上方 dp[2, 1] = 2、左上方 dp[2, 0] = 2,取最小值 2 加 1,写入 dp[3, 1] = 3。
编辑距离第 11 步:计算 dp[3, 1] 后的完整 dp 表 源前缀 / 目标前缀 j=0,空串 j=1,p j=2,pa j=3,pac j=4,pack i=0,空串 0,边界有效 1,边界有效 2,边界有效 3,边界有效 4,边界有效 i=1,b 1,边界有效 1,已计算 2,已计算 3,已计算 4,已计算 i=2,ba 2,边界有效 2,已计算 1,已计算 2,已计算 3,已计算 i=3,bag 3,边界有效 3,已计算 0,未计算初值 0,未计算初值 0,未计算初值 计算 dp[3, 2](源串 bag 转目标前缀 pa):最少 2 步
处理 i = 3, j = 2,求完整源串 bag 转为目标前缀 pa 的 dp[3, 2]:源尾字符 g 与目标尾字符 a 不同,比较左方 dp[3, 1] = 3、上方 dp[2, 2] = 1、左上方 dp[2, 1] = 2,取上方最小值 1(删除尾字符 g 归约到 ba 转 pa)加 1,写入 dp[3, 2] = 2。
编辑距离第 12 步:计算 dp[3, 2] 后的完整 dp 表 源前缀 / 目标前缀 j=0,空串 j=1,p j=2,pa j=3,pac j=4,pack i=0,空串 0,边界有效 1,边界有效 2,边界有效 3,边界有效 4,边界有效 i=1,b 1,边界有效 1,已计算 2,已计算 3,已计算 4,已计算 i=2,ba 2,边界有效 2,已计算 1,已计算 2,已计算 3,已计算 i=3,bag 3,边界有效 3,已计算 2,已计算 0,未计算初值 0,未计算初值 计算 dp[3, 3](源串 bag 转目标前缀 pac):最少 2 步
处理 i = 3, j = 3,求完整源串 bag 转为目标前缀 pac 的 dp[3, 3]:源尾字符 g 与目标尾字符 c 不同,比较左方 dp[3, 2] = 2、上方 dp[2, 3] = 2、左上方 dp[2, 2] = 1,取左上方最小值 1(将尾字符 g 替换为 c 归约到 ba 转 pa)加 1,写入 dp[3, 3] = 2。
编辑距离第 13 步:计算 dp[3, 3] 后的完整 dp 表 源前缀 / 目标前缀 j=0,空串 j=1,p j=2,pa j=3,pac j=4,pack i=0,空串 0,边界有效 1,边界有效 2,边界有效 3,边界有效 4,边界有效 i=1,b 1,边界有效 1,已计算 2,已计算 3,已计算 4,已计算 i=2,ba 2,边界有效 2,已计算 1,已计算 2,已计算 3,已计算 i=3,bag 3,边界有效 3,已计算 2,已计算 2,已计算 0,未计算初值 计算 dp[3, 4](源串 bag 转目标串 pack):最少 3 步
处理右下角 i = 3, j = 4,求完整源串 bag 转为完整目标串 pack 的 dp[3, 4]:源尾字符 g 与目标尾字符 k 不同,比较左方 dp[3, 3] = 2、上方 dp[2, 4] = 3、左上方 dp[2, 3] = 2,取最小值 2 加 1,写入 dp[3, 4] = 3,全表计算完成。
编辑距离第 14 步:计算 dp[3, 4] 后的完整 dp 表 源前缀 / 目标前缀 j=0,空串 j=1,p j=2,pa j=3,pac j=4,pack i=0,空串 0,边界有效 1,边界有效 2,边界有效 3,边界有效 4,边界有效 i=1,b 1,边界有效 1,已计算 2,已计算 3,已计算 4,已计算 i=2,ba 2,边界有效 2,已计算 1,已计算 2,已计算 3,已计算 i=3,bag 3,边界有效 3,已计算 2,已计算 2,已计算 3,已计算 读取右下角 dp[3, 4],返回最少编辑步数 3
全部状态转移结束后,单独突出右下角 dp[3, 4] = 3,作为将完整源串 bag 转换为完整目标串 pack 所需的最少编辑步数返回。本步不再更新其他格子;表给出最少步数,不唯一指定具体的编辑操作序列。
编辑距离第 15 步:返回结果的完整 dp 表 源前缀 / 目标前缀 j=0,空串 j=1,p j=2,pa j=3,pac j=4,pack i=0,空串 0,边界有效 1,边界有效 2,边界有效 3,边界有效 4,边界有效 i=1,b 1,边界有效 1,已计算 2,已计算 3,已计算 4,已计算 i=2,ba 2,边界有效 2,已计算 1,已计算 2,已计算 3,已计算 i=3,bag 3,边界有效 3,已计算 2,已计算 2,已计算 3,返回值
3. 空间优化¶
由于 \(dp[i,j]\) 是由上方 \(dp[i-1, j]\)、左方 \(dp[i, j-1]\)、左上方 \(dp[i-1, j-1]\) 转移而来的,而正序遍历会丢失左上方 \(dp[i-1, j-1]\) ,倒序遍历无法提前构建 \(dp[i, j-1]\) ,因此两种遍历顺序都不可取。
为此,我们可以使用一个变量 leftup 来暂存左上方的解 \(dp[i-1, j-1]\) ,从而只需考虑左方和上方的解。此时的情况与完全背包问题相同,可使用正序遍历。代码如下所示:
def edit_distance_dp_comp(s: str, t: str) -> int:
"""编辑距离:空间优化后的动态规划"""
n, m = len(s), len(t)
dp = [0] * (m + 1)
# 状态转移:首行
for j in range(1, m + 1):
dp[j] = j
# 状态转移:其余行
for i in range(1, n + 1):
# 状态转移:首列
leftup = dp[0] # 暂存 dp[i-1, j-1]
dp[0] += 1
# 状态转移:其余列
for j in range(1, m + 1):
temp = dp[j]
if s[i - 1] == t[j - 1]:
# 若两字符相等,则直接跳过此两字符
dp[j] = leftup
else:
# 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[j] = min(dp[j - 1], dp[j], leftup) + 1
leftup = temp # 更新为下一轮的 dp[i-1, j-1]
return dp[m]
/* 编辑距离:空间优化后的动态规划 */
int editDistanceDPComp(string s, string t) {
int n = s.length(), m = t.length();
vector<int> dp(m + 1, 0);
// 状态转移:首行
for (int j = 1; j <= m; j++) {
dp[j] = j;
}
// 状态转移:其余行
for (int i = 1; i <= n; i++) {
// 状态转移:首列
int leftup = dp[0]; // 暂存 dp[i-1, j-1]
dp[0] = i;
// 状态转移:其余列
for (int j = 1; j <= m; j++) {
int temp = dp[j];
if (s[i - 1] == t[j - 1]) {
// 若两字符相等,则直接跳过此两字符
dp[j] = leftup;
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[j] = min(min(dp[j - 1], dp[j]), leftup) + 1;
}
leftup = temp; // 更新为下一轮的 dp[i-1, j-1]
}
}
return dp[m];
}
/* 编辑距离:空间优化后的动态规划 */
int editDistanceDPComp(String s, String t) {
int n = s.length(), m = t.length();
int[] dp = new int[m + 1];
// 状态转移:首行
for (int j = 1; j <= m; j++) {
dp[j] = j;
}
// 状态转移:其余行
for (int i = 1; i <= n; i++) {
// 状态转移:首列
int leftup = dp[0]; // 暂存 dp[i-1, j-1]
dp[0] = i;
// 状态转移:其余列
for (int j = 1; j <= m; j++) {
int temp = dp[j];
if (s.charAt(i - 1) == t.charAt(j - 1)) {
// 若两字符相等,则直接跳过此两字符
dp[j] = leftup;
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[j] = Math.min(Math.min(dp[j - 1], dp[j]), leftup) + 1;
}
leftup = temp; // 更新为下一轮的 dp[i-1, j-1]
}
}
return dp[m];
}
/* 编辑距离:空间优化后的动态规划 */
int EditDistanceDPComp(string s, string t) {
int n = s.Length, m = t.Length;
int[] dp = new int[m + 1];
// 状态转移:首行
for (int j = 1; j <= m; j++) {
dp[j] = j;
}
// 状态转移:其余行
for (int i = 1; i <= n; i++) {
// 状态转移:首列
int leftup = dp[0]; // 暂存 dp[i-1, j-1]
dp[0] = i;
// 状态转移:其余列
for (int j = 1; j <= m; j++) {
int temp = dp[j];
if (s[i - 1] == t[j - 1]) {
// 若两字符相等,则直接跳过此两字符
dp[j] = leftup;
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[j] = Math.Min(Math.Min(dp[j - 1], dp[j]), leftup) + 1;
}
leftup = temp; // 更新为下一轮的 dp[i-1, j-1]
}
}
return dp[m];
}
/* 编辑距离:空间优化后的动态规划 */
func editDistanceDPComp(s string, t string) int {
n := len(s)
m := len(t)
dp := make([]int, m+1)
// 状态转移:首行
for j := 1; j <= m; j++ {
dp[j] = j
}
// 状态转移:其余行
for i := 1; i <= n; i++ {
// 状态转移:首列
leftUp := dp[0] // 暂存 dp[i-1, j-1]
dp[0] = i
// 状态转移:其余列
for j := 1; j <= m; j++ {
temp := dp[j]
if s[i-1] == t[j-1] {
// 若两字符相等,则直接跳过此两字符
dp[j] = leftUp
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[j] = MinInt(MinInt(dp[j-1], dp[j]), leftUp) + 1
}
leftUp = temp // 更新为下一轮的 dp[i-1, j-1]
}
}
return dp[m]
}
/* 编辑距离:空间优化后的动态规划 */
func editDistanceDPComp(s: String, t: String) -> Int {
let n = s.utf8CString.count
let m = t.utf8CString.count
var dp = Array(repeating: 0, count: m + 1)
// 状态转移:首行
for j in 1 ... m {
dp[j] = j
}
// 状态转移:其余行
for i in 1 ... n {
// 状态转移:首列
var leftup = dp[0] // 暂存 dp[i-1, j-1]
dp[0] = i
// 状态转移:其余列
for j in 1 ... m {
let temp = dp[j]
if s.utf8CString[i - 1] == t.utf8CString[j - 1] {
// 若两字符相等,则直接跳过此两字符
dp[j] = leftup
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[j] = min(min(dp[j - 1], dp[j]), leftup) + 1
}
leftup = temp // 更新为下一轮的 dp[i-1, j-1]
}
}
return dp[m]
}
/* 编辑距离:空间优化后的动态规划 */
function editDistanceDPComp(s, t) {
const n = s.length,
m = t.length;
const dp = new Array(m + 1).fill(0);
// 状态转移:首行
for (let j = 1; j <= m; j++) {
dp[j] = j;
}
// 状态转移:其余行
for (let i = 1; i <= n; i++) {
// 状态转移:首列
let leftup = dp[0]; // 暂存 dp[i-1, j-1]
dp[0] = i;
// 状态转移:其余列
for (let j = 1; j <= m; j++) {
const temp = dp[j];
if (s.charAt(i - 1) === t.charAt(j - 1)) {
// 若两字符相等,则直接跳过此两字符
dp[j] = leftup;
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[j] = Math.min(dp[j - 1], dp[j], leftup) + 1;
}
leftup = temp; // 更新为下一轮的 dp[i-1, j-1]
}
}
return dp[m];
}
/* 编辑距离:空间优化后的动态规划 */
function editDistanceDPComp(s: string, t: string): number {
const n = s.length,
m = t.length;
const dp = new Array(m + 1).fill(0);
// 状态转移:首行
for (let j = 1; j <= m; j++) {
dp[j] = j;
}
// 状态转移:其余行
for (let i = 1; i <= n; i++) {
// 状态转移:首列
let leftup = dp[0]; // 暂存 dp[i-1, j-1]
dp[0] = i;
// 状态转移:其余列
for (let j = 1; j <= m; j++) {
const temp = dp[j];
if (s.charAt(i - 1) === t.charAt(j - 1)) {
// 若两字符相等,则直接跳过此两字符
dp[j] = leftup;
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[j] = Math.min(dp[j - 1], dp[j], leftup) + 1;
}
leftup = temp; // 更新为下一轮的 dp[i-1, j-1]
}
}
return dp[m];
}
/* 编辑距离:空间优化后的动态规划 */
int editDistanceDPComp(String s, String t) {
int n = s.length, m = t.length;
List<int> dp = List.filled(m + 1, 0);
// 状态转移:首行
for (int j = 1; j <= m; j++) {
dp[j] = j;
}
// 状态转移:其余行
for (int i = 1; i <= n; i++) {
// 状态转移:首列
int leftup = dp[0]; // 暂存 dp[i-1, j-1]
dp[0] = i;
// 状态转移:其余列
for (int j = 1; j <= m; j++) {
int temp = dp[j];
if (s[i - 1] == t[j - 1]) {
// 若两字符相等,则直接跳过此两字符
dp[j] = leftup;
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[j] = min(min(dp[j - 1], dp[j]), leftup) + 1;
}
leftup = temp; // 更新为下一轮的 dp[i-1, j-1]
}
}
return dp[m];
}
/* 编辑距离:空间优化后的动态规划 */
fn edit_distance_dp_comp(s: &str, t: &str) -> i32 {
let (n, m) = (s.len(), t.len());
let mut dp = vec![0; m + 1];
// 状态转移:首行
for j in 1..m {
dp[j] = j as i32;
}
// 状态转移:其余行
for i in 1..=n {
// 状态转移:首列
let mut leftup = dp[0]; // 暂存 dp[i-1, j-1]
dp[0] = i as i32;
// 状态转移:其余列
for j in 1..=m {
let temp = dp[j];
if s.chars().nth(i - 1) == t.chars().nth(j - 1) {
// 若两字符相等,则直接跳过此两字符
dp[j] = leftup;
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[j] = std::cmp::min(std::cmp::min(dp[j - 1], dp[j]), leftup) + 1;
}
leftup = temp; // 更新为下一轮的 dp[i-1, j-1]
}
}
dp[m]
}
/* 编辑距离:空间优化后的动态规划 */
int editDistanceDPComp(char *s, char *t, int n, int m) {
int *dp = calloc(m + 1, sizeof(int));
// 状态转移:首行
for (int j = 1; j <= m; j++) {
dp[j] = j;
}
// 状态转移:其余行
for (int i = 1; i <= n; i++) {
// 状态转移:首列
int leftup = dp[0]; // 暂存 dp[i-1, j-1]
dp[0] = i;
// 状态转移:其余列
for (int j = 1; j <= m; j++) {
int temp = dp[j];
if (s[i - 1] == t[j - 1]) {
// 若两字符相等,则直接跳过此两字符
dp[j] = leftup;
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[j] = myMin(myMin(dp[j - 1], dp[j]), leftup) + 1;
}
leftup = temp; // 更新为下一轮的 dp[i-1, j-1]
}
}
int res = dp[m];
// 释放内存
free(dp);
return res;
}
/* 编辑距离:空间优化后的动态规划 */
fun editDistanceDPComp(s: String, t: String): Int {
val n = s.length
val m = t.length
val dp = IntArray(m + 1)
// 状态转移:首行
for (j in 1..m) {
dp[j] = j
}
// 状态转移:其余行
for (i in 1..n) {
// 状态转移:首列
var leftup = dp[0] // 暂存 dp[i-1, j-1]
dp[0] = i
// 状态转移:其余列
for (j in 1..m) {
val temp = dp[j]
if (s[i - 1] == t[j - 1]) {
// 若两字符相等,则直接跳过此两字符
dp[j] = leftup
} else {
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[j] = min(min(dp[j - 1], dp[j]), leftup) + 1
}
leftup = temp // 更新为下一轮的 dp[i-1, j-1]
}
}
return dp[m]
}
### 编辑距离:空间优化后的动态规划 ###
def edit_distance_dp_comp(s, t)
n, m = s.length, t.length
dp = Array.new(m + 1, 0)
# 状态转移:首行
(1...(m + 1)).each { |j| dp[j] = j }
# 状态转移:其余行
for i in 1...(n + 1)
# 状态转移:首列
leftup = dp.first # 暂存 dp[i-1, j-1]
dp[0] += 1
# 状态转移:其余列
for j in 1...(m + 1)
temp = dp[j]
if s[i - 1] == t[j - 1]
# 若两字符相等,则直接跳过此两字符
dp[j] = leftup
else
# 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
dp[j] = [dp[j - 1], dp[j], leftup].min + 1
end
leftup = temp # 更新为下一轮的 dp[i-1, j-1]
end
end
dp[m]
end