每日一题——编辑距离

编辑距离 参考资料题目描述示例 解题思路动态规划（DP）方法 代码实现复杂度分析示例详解示例1：`"nowcoder"` → `"new"`示例2：`"intention"` → `"execution"` 总结与心得

参考资料

建议先参考下面一个视频和文档，然后再思考问题，不然很容易会被吓到。 ——

programmercarl /0072.%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

题目描述

给定两个字符串 str1 和 str2，计算将 str1 转换为 str2 所需的最小操作次数。每次操作可以执行以下三种操作之一：

插入一个字符删除一个字符修改一个字符 示例 示例1: 输入："nowcoder", "new"输出：6解释：修改 ‘o’ 为 ‘e’，删除后续5个字符 示例2: 输入："intention", "execution"输出：5解释：需要修改前5个字符 解题思路 动态规划（DP）方法

状态定义

dp[i][j] 表示将 str1 的前 i 个字符转换为 str2 的前 j 个字符所需的最小操作次数

状态转移方程

当 str1[i-1] == str2[j-1] 时：dp[i][j] = dp[i-1][j-1]否则，取三种操作的最小值加1： 修改操作：dp[i-1][j-1] + 1插入操作：dp[i][j-1] + 1删除操作：dp[i-1][j] + 1

初始化

dp[i][0] = i：表示删除操作dp[0][j] = j：表示插入操作 代码实现 #include <string.h> // 引入字符串处理函数库，用于调用strlen等函数 // 辅助函数：计算三个整数中的最小值 int min(int a, int b, int c) { // 使用三元运算符实现最小值计算 // 首先比较a和b，取较小值，再与c比较，最终返回最小值 return a < b ? (a < c ? a : c) : (b < c ? b : c); } // 主函数：计算两个字符串之间的编辑距离 int editDistance(char* str1, char* str2) { // 获取两个字符串的长度 int len1 = strlen(str1); // str1的长度 int len2 = strlen(str2); // str2的长度 // 处理空字符串情况 // 如果str1为空，将str2的所有字符插入到str1中，需要len2次操作 if (len1 == 0) return len2; // 如果str2为空，将str1的所有字符删除，需要len1次操作 if (len2 == 0) return len1; // 创建动态规划表dp，大小为(len1+1)×(len2+1) // dp[i][j]表示str1的前i个字符转换为str2的前j个字符所需的最小操作数 int dp[len1 + 1][len2 + 1]; // 初始化动态规划表的第一行和第一列 // dp[i][0]：将str1的前i个字符转换为空字符串，需要i次删除操作 for (int i = 0; i <= len1; i++) dp[i][0] = i; // dp[0][j]：将空字符串转换为str2的前j个字符，需要j次插入操作 for (int j = 0; j <= len2; j++) dp[0][j] = j; // 动态规划过程：填充dp表 // 遍历str1和str2的每个字符 for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) { // 如果当前字符相同，不需要额外操作，直接继承左上角的值 if (str1[i - 1] == str2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { // 如果当前字符不同，选择三种操作的最小值 + 1 // dp[i - 1][j - 1]：替换操作 // dp[i][j - 1]：插入操作 // dp[i - 1][j]：删除操作 dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1; } } } // 返回最终的编辑距离，即dp表右下角的值 return dp[len1][len2]; } 复杂度分析 时间复杂度：O(mn)，其中m和n分别是两个字符串的长度空间复杂度：O(mn)，需要一个二维数组存储动态规划的状态 示例详解 示例1："nowcoder" → "new" 对于第一个位置，两个字符串都是’n’，不需要操作第二个位置，需要将’o’修改为’e’，操作数+1接下来需要删除"wcoder"这5个字符，每个字符删除操作数+1最终需要6次操作 示例2："intention" → "execution" 两个字符串后缀"tion"相同，不需要操作需要修改前5个字符，每个字符修改操作数+1最终需要5次操作 总结与心得

这道题虽然看起来操作较多（增删改），但实际难度适中，比起IP地址字符串转换的题目要简单一些。关键在于理解动态规划的状态设计：

一开始可能会想直接用m×n的dp数组（去掉第一行第一列），但这样是不行的。因为如果两个字符串完全相同，结果应该是0，所以需要包含这种情况。

初始化很重要：第一行和第一列分别表示纯粹的删除和插入操作，这为后续的状态转移奠定了基础。

状态转移方程的设计体现了问题的本质：当字符相同时不需要操作，当字符不同时取三种操作的最小值。