文章目录
- HJ52 计算字符串的编辑距离
- 描述
- 输入描述
- 输出描述
- 示例1
- HJ52 计算字符串的编辑距离
- 描述
- 输入描述
- 输出描述
- 示例1
- 解题思路
- 算法分析
- 动态规划状态转移
- 状态转移方程
- 算法流程图
- DP表格示例
- 三种操作详解
- 代码实现思路
- 时间复杂度分析
- 关键优化技巧
- 实际应用场景
- 算法扩展
- 面试考点
- 完整题解代码
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距离）。主要涉及：
- 状态定义：dp[i][j]表示s[0:i]和t[0:j]的编辑距离
- 状态转移：根据字符是否相同选择最优操作
- 边界处理：空字符串的初始化
- 空间优化：滚动数组优化空间复杂度
动态规划状态转移
状态转移方程
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 加一]
代码实现思路
-
基础DP版本：
- 二维数组存储所有状态
- 时间复杂度O(mn)，空间复杂度O(mn)
- 易于理解和调试
-
空间优化版本：
- 滚动数组优化空间
- 时间复杂度O(mn)，空间复杂度O(min(m,n))
- 适用于大规模数据
-
记忆化递归版本：
- 自顶向下的思考方式
- 代码更直观，容易理解递归关系
- 适合面试讲解
时间复杂度分析
| 算法版本 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 基础DP | O(mn) | O(mn) | 经典实现 |
| 空间优化 | O(mn) | O(min(m,n)) | 节省空间 |
| 记忆化递归 | O(mn) | O(mn) | 易于理解 |
关键优化技巧
-
空间优化：
// 只需要两行数组 prev := make([]int, m+1) curr := make([]int, m+1) -
字符串长度优化：
// 确保s是较短的字符串 if m > n {s, t = t, sm, n = n, m } -
边界条件处理：
// 空字符串的初始化 dp[0][j] = j // 需要j次插入 dp[i][0] = i // 需要i次删除
实际应用场景
- 文本相似度计算：搜索引擎的模糊匹配
- 拼写检查：单词纠错功能
- DNA序列比对：生物信息学中的序列分析
- 版本控制：Git中的文件差异比较
- 自然语言处理：文本相似度度量
算法扩展
面试考点
- 状态定义能力：正确定义DP状态
- 状态转移推导：理解三种操作的含义
- 边界条件处理：空字符串的初始化
- 空间优化思维：滚动数组的使用
- 实际应用理解：算法的实际价值
这个问题是动态规划的经典应用，展示了如何将复杂问题分解为子问题，并通过状态转移方程求解最优解。编辑距离算法在实际工程中有广泛应用，是面试中的高频考点。
完整题解代码
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
}
)
