【Hot 100 刷题计划】 LeetCode 72. 编辑距离 | C++ 经典 DP 增删改状态转移
LeetCode 72. 编辑距离
📌 题目描述
题目级别：困难 (大厂极高频)
给你两个单词word1和word2， 请返回将word1转换成word2所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
- 示例 1:
输入：word1 = "horse",word2 = "ros"
输出：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)
💡 破题思路：二维动态规划
编辑距离是字符串 DP 的终极 Boss，但只要拆解开它的状态转移，逻辑其实非常清晰。
状态定义：
定义f[i][j]表示：将word1的前i个字符转换成word2的前j个字符所需要的最少操作步数。
状态转移推导：
当我们考察word1的第i个字符和word2的第j个字符时，我们有三种基础操作路线：
- 删除：假设我们已经把
word1的前i-1个字符变成了word2的前j个字符，那么我们只需要把word1多出来的第i个字符删除即可。代价：f[i - 1][j] + 1。 - 插入：假设我们已经把
word1的前i个字符变成了word2的前j-1个字符，那么我们只需要再插入一个word2的第j个字符即可。代价：f[i][j - 1] + 1。 - 替换/跳过：假设我们已经把
word1的前i-1变成了word2的前j-1：- 如果当前字符相等（
word1[i] == word2[j]），不需要操作，直接跳过。代价：f[i - 1][j - 1] + 0。 - 如果当前字符不等，我们需要做替换操作。代价：
f[i - 1][j - 1] + 1。
- 如果当前字符相等（
我们取这三条路线中的最小值即可！
本解法高光点（哨兵技巧与边界处理）：
代码中使用了word1 = " " + word1;加入空格哨兵，让真实字符从下标1开始，完美避免了i-1越界。
同时，必须正确初始化边界：
f[i][0] = i：把长度为i的字符串变成空串，必须删除i次。f[0][j] = j：把空串变成长度为j的字符串，必须插入j次。
💻 C++ 代码实现 (标准二维 DP)
classSolution{public:intminDistance(string word1,string word2){intm=word1.size(),n=word2.size();// 极客技巧：头部垫一个空格，让后续有效字符下标从 1 开始word1=" "+word1;word2=" "+word2;intf[m+10][n+10];// 初始化为一个较大值memset(f,0x3f3f3f3f,sizeoff);// 边界初始化极其重要！// word1 的前 i 个字符变为空串，需要删除 i 次for(inti=0;i<=m;i++)f[i][0]=i;// 空串变成 word2 的前 j 个字符，需要插入 j 次for(intj=0;j<=n;j++)f[0][j]=j;// 遍历填写二维表格for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){// 路线 1 & 2：从上方下来（删除），或从左方过来（插入）f[i][j]=min(f[i-1][j],f[i][j-1])+1;// 路线 3：从左上角过来（替换或直接匹配跳过）// 因为前面垫了空格，这里的下标直接用 i 和 jintcost=(word1[i]==word2[j]?0:1);f[i][j]=min(f[i][j],f[i-1][j-1]+cost);}}returnf[m][n];}};