ChatGPT 写代码还是可以的，不过在一步一步推导过程中就会错误频出了。
编辑距离是一种用来度量两个字符串之间相似程度的算法。它通常用于搜索错别字的纠正，或者模糊搜索。例如，如果我们搜索 gogle 时，它可以正确搜索到 google 的结果。
算法原理
编辑距离通过将一个字符串转换成另一个字符串所需的最少操作数来衡量两个字符串的相似度。这些操作可以是插入一个字符、删除一个字符或替换一个字符。
编辑距离的实现是通过动态规划来做的，那就让我们来看看如何用动态规划来拆分子问题。
具体来说，我们可以把两个字符串看成是由它们的子串组成的，那么问题就变成了如何计算这些子串之间的编辑距离。我们可以先计算最小的子串之间的编辑距离，然后再逐渐扩大子串的范围，直到计算出整个字符串的编辑距离。这样，我们就把大问题拆分成了很多个小问题。
我们假设两个字符串分别为 A 和 B, 当我们需要计算A 的前 i 个字符到 B 的前 j 个字符的编辑距离dp[i][j]时，我们需要考虑以下三种情况：
- 如果
A[i] == B[i], 则其编辑距离就等于dp[i-1][j-1] - 如果
A[i] != B[i]，则要分三种情况，然后取三种情况的最小值就是编辑距离：
- 如果将 A 的第 i 个字符替换为 B 的第 j 个字符，那么编辑距离就是
dp[i-1][j-1] + 1。 - 如果将 A 的第 i 个字符删除，那么编辑距离就是
dp[i-1][j] + 1。 - 如果将 B 的第 j 个字符插入到 A 的第 i 个字符之后，那么编辑距离就是
dp[i][j-1] + 1。
举个例子
假设 A 为 abcd，B 为 abedf。我们来一步一步看它的编辑距离是怎么计算的。
首先，我们创建一个表格：
| 空 | a | b | e | d | f | |
| 空 | 0 | 1 | 2 | 3 | 4 | 5 |
| a | 1 | x | ||||
| b | 2 | |||||
| c | 3 | |||||
| d | 4 |
表格中的值 dp[i][j] 就 A 的前 i 的字符到 B 的前 j 个字符的编辑距离。我们首先填充第一行和第一列，因为从空字符串转换到一个字符串的编辑距离就是进行该字符串长度的插入。这个就简单了。
例如这个时候我们要计算 x 位置的编辑距离， 我们就可以带入上面的那几种情况：
因为 A 和 B 在 x 位置的都为 a，所以其编辑距离就等于 d[i-1][j-1], 也就是 0， 我们将其更新到表格中
| 空 | a | b | e | d | f | |
| 空 | 0 | 1 | 2 | 3 | 4 | 5 |
| a | 1 | 0 | x | |||
| b | 2 | |||||
| c | 3 | |||||
| d | 4 |
接下来我们就可以计算新的 x 位置的编辑距离了，由于此时 A[i] != B[j] 了， 我们就要按前文说的分三种情况分别计算了：
- 替换:
dp[i-1][j-1] + 1 = 1 + 1 = 2 - 删除：
dp[i-1][j] + 1 = 2 + 1 = 3 - 插入：
dp[i][j-1] + 1 = 0 + 1 = 1
所以我们可以取得最小值为 1，然后写入表格
| 空 | a | b | e | d | f | |
| 空 | 0 | 1 | 2 | 3 | 4 | 5 |
| a | 1 | 0 | 1 | x | ||
| b | 2 | |||||
| c | 3 | |||||
| d | 4 |
重复上面的步骤，我们就可以得到最终的结果
| 空 | a | b | e | d | f | |
| 空 | 0 | 1 | 2 | 3 | 4 | 5 |
| a | 1 | 0 | 1 | 2 | 3 | 4 |
| b | 2 | 1 | 0 | 1 | 2 | 3 |
| c | 3 | 2 | 1 | 1 | 2 | 3 |
| d | 4 | 3 | 2 | 2 | 1 | 2 |
因此我们就可以得到最终的编辑距离为 2 了。
如果理解了上述过程，写代码就是个翻译过程了。
代码实现
koltin
fun editDistance(s: String, t: String): Int { val m = s.length val n = t.length val dp = Array(m+1) { IntArray(n+1) } for (i in 0..m) { dp[i][0] = i } for (j in 0..n) { dp[0][j] = j } for (i in 1..m) { for (j in 1..n) { if (s[i-1] == t[j-1]) { dp[i][j] = dp[i-1][j-1] } else { dp[i][j] = minOf(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1 } } } return dp[m][n] }
rn dp[m][n]}
Rust 实现
fn edit_distance(s: &str, t: &str) -> usize { let m = s.chars().count(); let n = t.chars().count(); let mut dp = vec![vec![0; n+1]; m+1]; for i in 0..=m { dp[i][0] = i; } for j in 0..=n { dp[0][j] = j; } for i in 1..=m { for j in 1..=n { if s.chars().nth(i-1) == t.chars().nth(j-1) { dp[i][j] = dp[i-1][j-1]; } else { dp[i][j] = dp[i-1][j-1].min(dp[i][j-1]).min(dp[i-1][j]) + 1; } } } dp[m][n] }
接下来让我们分析下复杂度：
在上面的实现中，我们使用了一个二维数组 dp 来存储每个子问题的编辑距离。因此，算法的空间复杂度为 O(mn)，其中 m 和 n 分别是两个字符串的长度。
在算法的时间复杂度方面，我们需要遍历每个子问题，并对它们进行一些操作（比较两个字符是否相等、取最小值等）。因此，时间复杂度为 O(mn)。
算法优化
如果我们看上面流程，我们是一行一行的去计算，而每一行的计算只依赖于几个特定点的值，因而我们可以使用滚动数组技巧将空间复杂度降至 O(n)。
Kotlin 实现
fun editDistance(s: String, t: String): Int { val m = s.length val n = t.length val dp = IntArray(n + 1) { it } var pre: Int var temp: Int for (i in 1..m) { pre = dp[0] dp[0] = i for (j in 1..n) { temp = dp[j] dp[j] = (pre + (s[i - 1] != t[j - 1]).toInt()) .coerceAtMost(dp[j - 1] + 1) .coerceAtMost(dp[j] + 1) pre = temp } } return dp[n] }
Rust 实现
fn edit_distance(s: &str, t: &str) -> usize { let m = s.len(); let n = t.len(); let mut dp = vec![0; n + 1]; for j in 0..=n { dp[j] = j; } for i in 1..=m { let mut pre = dp[0]; dp[0] = i; for j in 1..=n { let temp = dp[j]; dp[j] = (pre + (s.as_bytes()[i - 1] != t.as_bytes()[j - 1]) as usize) .min((dp[j - 1] + 1).min(dp[j] + 1)); pre = temp; } } dp[n] }
