HJ52 计算字符串的编辑距离

描述

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转变成另一个所需的最少单字符编辑操作次数。被允许的转变包括：

• 对于任意一个字符串，在任意位置插入一个字符；
• 对于任意一个字符串，删除任意一个字符；
• 对于任意一个字符串，替换任意一个字符。

现在，对于给定的字符串 s 和 t，请计算出它们的编辑距离。

输入描述

第一行输入一个长度为 1<=len(s)<=10^3，仅由小写字母组成的字符串 s。
第二行输入一个长度为 1<=len(t)<=10^3，仅由小写字母组成的字符串 t。

输出描述

输出一个整数，表示 s 和 t 的编辑距离。

示例1

输入：
abcdefg
abcdef

输出：
1

说明：
在这个样例中，可以选择将 s 末尾的 ‘g’ 删除。当然，也可以选择在 t 末尾插入 ‘g’。

HJ52 计算字符串的编辑距离

描述

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转变成另一个所需的最少单字符编辑操作次数。被允许的转变包括：

• 对于任意一个字符串，在任意位置插入一个字符；
• 对于任意一个字符串，删除任意一个字符；
• 对于任意一个字符串，替换任意一个字符。

现在，对于给定的字符串 s 和 t，请计算出它们的编辑距离。

输入描述

第一行输入一个长度为 1<=len(s)<=10^3，仅由小写字母组成的字符串 s。
第二行输入一个长度为 1<=len(t)<=10^3，仅由小写字母组成的字符串 t。

输出描述

输出一个整数，表示 s 和 t 的编辑距离。

示例1

输入：
abcdefg
abcdef

输出：
1

说明：
在这个样例中，可以选择将 s 末尾的 ‘g’ 删除。当然，也可以选择在 t 末尾插入 ‘g’。

解题思路

算法分析

这道题是经典的动态规划问题——编辑距离（Levenshtein距离）。主要涉及：

1. 状态定义：dp[i][j]表示s[0:i]和t[0:j]的编辑距离
2. 状态转移：根据字符是否相同选择最优操作
3. 边界处理：空字符串的初始化
4. 空间优化：滚动数组优化空间复杂度

动态规划状态转移

状态转移方程

graph LRA[状态转移方程] --> B[状态 dp_i_j]B --> C{当前字符是否相同}C -->|相同| D[继承左上状态 dp_i_减1_j_减1]C -->|不同| E[三种操作取最小值]E --> F[删除：删除 s_第_i_个字符]E --> G[插入：插入 t_第_j_个字符]E --> H[替换：将 s_第_i_个字符替换为 t_第_j_个]

算法流程图

flowchart TDA[读取字符串 s 和 t] --> B[获取长度：m 是 s 的长度，n 是 t 的长度]B --> C[创建 dp 数组，大小为 m 加 1 乘以 n 加 1]C --> D[初始化边界条件]D --> E[第 0 行：dp_0_j 设为 j，遍历所有 j]E --> F[第 0 列：dp_i_0 设为 i，遍历所有 i]F --> G[进入双重循环，填充 dp 表]G --> H{当前 s 的第 i 个字符是否等于 t 的第 j 个字符}H -->|是| I[dp_i_j 设为 dp_i_减1_j_减1]H -->|否| J[dp_i_j 设为三种操作中的最小值]I --> K{是否循环结束}J --> KK -->|否| GK -->|是| L[返回最终结果 dp_m_n]

DP表格示例

以s=“abc”, t="ab"为例：

graph TDA[DP 表格构建过程] --> B[构造完整 DP 数组并填充]B --> C[每个 dp_i_j 代表编辑距离]C --> D[完成后，查看 dp_3_2 的值]D --> E[最终答案：dp_3_2 等于 1]

三种操作详解

graph TDA[编辑操作] --> B[插入操作]A --> C[删除操作]A --> D[替换操作]B --> E[在字符串 s 中插入字符]B --> F[代价：dp_i_j减1 加一]C --> G[从字符串 s 中删除字符]C --> H[代价：dp_i减1_j 加一]D --> I[将 s 中字符替换为 t 中字符]D --> J[代价：dp_i减1_j减1 加一]

代码实现思路

1. 基础DP版本：

   • 二维数组存储所有状态
   • 时间复杂度O(mn)，空间复杂度O(mn)
   • 易于理解和调试

2. 空间优化版本：

   • 滚动数组优化空间
   • 时间复杂度O(mn)，空间复杂度O(min(m,n))
   • 适用于大规模数据

3. 记忆化递归版本：

   • 自顶向下的思考方式
   • 代码更直观，容易理解递归关系
   • 适合面试讲解

时间复杂度分析

算法版本	时间复杂度	空间复杂度	特点
基础DP	O(mn)	O(mn)	经典实现
空间优化	O(mn)	O(min(m,n))	节省空间
记忆化递归	O(mn)	O(mn)	易于理解

关键优化技巧

1. 空间优化：

   // 只需要两行数组
   prev := make([]int, m+1)
   curr := make([]int, m+1)
   

2. 字符串长度优化：

   // 确保s是较短的字符串
   if m > n {s, t = t, sm, n = n, m
   }
   

3. 边界条件处理：

   // 空字符串的初始化
   dp[0][j] = j  // 需要j次插入
   dp[i][0] = i  // 需要i次删除
   

实际应用场景

1. 文本相似度计算：搜索引擎的模糊匹配
2. 拼写检查：单词纠错功能
3. DNA序列比对：生物信息学中的序列分析
4. 版本控制：Git中的文件差异比较
5. 自然语言处理：文本相似度度量

算法扩展

面试考点

1. 状态定义能力：正确定义DP状态
2. 状态转移推导：理解三种操作的含义
3. 边界条件处理：空字符串的初始化
4. 空间优化思维：滚动数组的使用
5. 实际应用理解：算法的实际价值

这个问题是动态规划的经典应用，展示了如何将复杂问题分解为子问题，并通过状态转移方程求解最优解。编辑距离算法在实际工程中有广泛应用，是面试中的高频考点。

完整题解代码

package mainimport ("fmt"
)func main() {var s, t stringfmt.Scanln(&s)fmt.Scanln(&t)result := editDistance(s, t)fmt.Println(result)
}// editDistance 计算两个字符串的编辑距离
// 使用动态规划算法，时间复杂度O(mn)，空间复杂度O(mn)
func editDistance(s, t string) int {m, n := len(s), len(t)// dp[i][j] 表示 s[0:i] 和 t[0:j] 的编辑距离dp := make([][]int, m+1)for i := range dp {dp[i] = make([]int, n+1)}// 初始化边界条件// s为空字符串时，需要插入t的所有字符for j := 0; j <= n; j++ {dp[0][j] = j}// t为空字符串时，需要删除s的所有字符for i := 0; i <= m; i++ {dp[i][0] = i}// 动态规划填表for i := 1; i <= m; i++ {for j := 1; j <= n; j++ {if s[i-1] == t[j-1] {// 字符相同，不需要操作dp[i][j] = dp[i-1][j-1]} else {// 字符不同，取三种操作的最小值dp[i][j] = min(dp[i-1][j]+1,   // 删除s[i-1]dp[i][j-1]+1,   // 插入t[j-1]dp[i-1][j-1]+1, // 替换s[i-1]为t[j-1])}}}return dp[m][n]
}// 空间优化版本：只使用O(min(m,n))空间
func editDistanceOptimized(s, t string) int {m, n := len(s), len(t)// 确保s是较短的字符串，优化空间使用if m > n {s, t = t, sm, n = n, m}// 只需要两行：当前行和上一行prev := make([]int, m+1)curr := make([]int, m+1)// 初始化第一行for i := 0; i <= m; i++ {prev[i] = i}// 逐行计算for j := 1; j <= n; j++ {curr[0] = j // 边界条件for i := 1; i <= m; i++ {if s[i-1] == t[j-1] {curr[i] = prev[i-1]} else {curr[i] = min(prev[i]+1,   // 删除curr[i-1]+1, // 插入prev[i-1]+1, // 替换)}}// 交换prev和currprev, curr = curr, prev}return prev[m]
}// 递归+记忆化版本（展示不同实现思路）
func editDistanceMemo(s, t string) int {m, n := len(s), len(t)memo := make([][]int, m+1)for i := range memo {memo[i] = make([]int, n+1)for j := range memo[i] {memo[i][j] = -1}}var dfs func(i, j int) intdfs = func(i, j int) int {// 边界条件if i == 0 {return j}if j == 0 {return i}// 记忆化if memo[i][j] != -1 {return memo[i][j]}if s[i-1] == t[j-1] {memo[i][j] = dfs(i-1, j-1)} else {memo[i][j] = min(dfs(i-1, j)+1,   // 删除dfs(i, j-1)+1,   // 插入dfs(i-1, j-1)+1, // 替换)}return memo[i][j]}return dfs(m, n)
}// min 返回三个数中的最小值
func min(a, b, c int) int {if a <= b && a <= c {return a}if b <= c {return b}return c
}// 用于两个数的min函数
func min2(a, b int) int {if a < b {return a}return b
}