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){intmword1.size(),nword2.size();// 极客技巧头部垫一个空格让后续有效字符下标从 1 开始word1 word1;word2 word2;intf[m10][n10];// 初始化为一个较大值memset(f,0x3f3f3f3f,sizeoff);// 边界初始化极其重要// word1 的前 i 个字符变为空串需要删除 i 次for(inti0;im;i)f[i][0]i;// 空串变成 word2 的前 j 个字符需要插入 j 次for(intj0;jn;j)f[0][j]j;// 遍历填写二维表格for(inti1;im;i){for(intj1;jn;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];}};