LeetCode 72：编辑距离（Edit Distance）—— 题解

LeetCode 72编辑距离Edit Distance—— 题解 ✅ 题目链接 https://leetcode.cn/problems/edit-distance/ 内容概要给定两个字符串word1和word2你可以对word1执行以下三种操作之一插入一个字符删除一个字符替换一个字符返回将word1转换成word2所需的最少操作次数。✅ 经典二维 DP✅ 面试 Hard 必考题✅ 字符串 DP 的巅峰之作 解题思路核心一、DP 状态定义必须背dp[i][j]将 word1 的前 i 个字符 转换成 word2 的前 j 个字符 所需的最少操作次数二、初始化边界条件情况含义值dp[i][0]删光word1idp[0][j]插入word2jfor(inti0;ilen1;i)dp[i][0]i;for(intj0;jlen2;j)dp[0][j]j; 状态转移灵魂✅ 情况 1当前字符相同if(w1[i-1]w2[j-1]){dp[i][j]dp[i-1][j-1];}不需要任何操作直接继承之前的状态❌ 情况 2当前字符不同三种操作取最小值操作状态来源含义替换dp[i-1][j-1] 1改字符删除dp[i-1][j] 1删word1[i]插入dp[i][j-1] 1插word2[j]实际上删除和插入是相对的插word2[j]和删word2[j]是等价的dp[i][j]Math.min(Math.min(dp[i-1][j]1,// 删除dp[i][j-1]1// 插入),dp[i-1][j-1]1// 替换);✅ AC 代码Java完全基于你的代码classSolution{publicintminDistance(Stringword1,Stringword2){char[]w1word1.toCharArray();char[]w2word2.toCharArray();intlen1word1.length();intlen2word2.length();int[][]dpnewint[len11][len21];// 初始化for(inti0;ilen1;i)dp[i][0]i;for(intj0;jlen2;j)dp[0][j]j;// 状态转移for(inti1;ilen1;i){for(intj1;jlen2;j){if(w1[i-1]w2[j-1]){dp[i][j]dp[i-1][j-1];}else{dp[i][j]Math.min(Math.min(dp[i-1][j]1,// 删除dp[i][j-1]1// 插入),dp[i-1][j-1]1// 替换);}}}returndp[len1][len2];}}⏱️ 复杂度分析指标复杂度时间复杂度O(n × m)空间复杂度O(n × m)✅ 一句话总结编辑距离 用 DP 枚举“增 / 删 / 替”三种操作的最小代价。 面试加分点建议背✅ 为什么初始化是dp[i][0] i✅ 为什么替换是dp[i-1][j-1] 1✅ 插入和删除为什么对称✅ 如何用滚动数组优化到 O(min(n, m))