企业官网建设流程全解析

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 个字符 所需的最少操作次数

二、初始化（边界条件）

for(inti=0;i<=len1;i++)dp[i][0]=i;for(intj=0;j<=len2;j++)dp[0][j]=j;

🔁 状态转移（灵魂）

✅ 情况 1：当前字符相同

if(w1[i-1]==w2[j-1]){dp[i][j]=dp[i-1][j-1];}

• 不需要任何操作
• 直接继承之前的状态

❌ 情况 2：当前字符不同

三种操作取最小值：

实际上，删除和插入是相对的，插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[]w1=word1.toCharArray();char[]w2=word2.toCharArray();intlen1=word1.length();intlen2=word2.length();int[][]dp=newint[len1+1][len2+1];// 初始化for(inti=0;i<=len1;i++)dp[i][0]=i;for(intj=0;j<=len2;j++)dp[0][j]=j;// 状态转移for(inti=1;i<=len1;i++){for(intj=1;j<=len2;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];}}

⏱️ 复杂度分析

✅ 一句话总结

编辑距离 = 用 DP 枚举“增 / 删 / 替”三种操作的最小代价。

📌 面试加分点（建议背）

• ✅ 为什么初始化是dp[i][0] = i
• ✅ 为什么替换是dp[i-1][j-1] + 1
• ✅ 插入和删除为什么对称
• ✅ 如何用滚动数组优化到 O(min(n, m))