LeetCode、72. 编辑距离【中等，二维DP】
文章目录
- 前言
- LeetCode、72. 编辑距离【中等，二维DP】
- 题目链接与分类
- 二维DP
- 资料获取
前言
博主介绍：✌目前全网粉丝2W+，csdn博客专家、Java领域优质创作者，博客之星、阿里云平台优质作者、专注于Java后端技术领域。
涵盖技术内容：Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。
博主所有博客文件目录索引：博客目录索引(持续更新)
视频平台：b站-Coder长路
LeetCode、72. 编辑距离【中等，二维DP】
题目链接与分类
题目链接：LeetCode、72. 编辑距离
分类：动态规划/二维DP
二维DP
思路：动态规划
dp数组含义：dp[i][j]表示a串的[0,i]字符串替换为b串的[0,j]例如：abc->ab，即为dp[3][2]。示例：abd abcd ' ' a b c d '' 0 1 2 3 4 a 1 0 1 2 3 b 2 1 0 1 2d 3 2 1 1 1 此时最后一个dp[3][4]就表示abd=>abcd的最终情况计算dp[1][2] 实际上就是a => ab,由于a!=b，那么此时可以进行三种情况： ①添加操作dp[1][2] = dp[1][1]+1，实际上就是将a替换为a，然后添加b，构成ab。②删除操作dp[1][2] = dp[0][2]+1，实际上就是空字符串替换为ab，此时为abb，删除最后一个，此时构成ab。③替换操作dp[1][2] = dp[0][1]+1，实际上空字符串替换得到a，此时为aa，那么替换最后一个a为b，此时构成ab。转移方程：
1、dp[i][j] = dp[i - 1][j - 1], a[i] == b[j]
2、dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1 , a[i] != b[j]边界值：
dp[i][0] = i, dp[0][j] = j
复杂度分析：时间复杂度O(n*m)；空间复杂度O(n*m)
class Solution {//定义：dp(i,j) 前i个匹配前j个最小编辑的个数//ch1 = ch2 dp(i,j) = dp(i - 1, j - 1)//ch1 != ch2 dp(i, j) = Math.min(dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1)) + 1public int minDistance(String word1, String word2) {int n = word1.length(), m = word2.length();int[][] dp = new int[n + 1][m + 1];//初始化 字符串1需要新增i个 或者 字符串2需要删除i个for (int i = 0; i <= n; i ++) {dp[i][0] = i;}//初始化 同上for (int j = 0; j <= m; j ++) {dp[0][j] = j;}//递推方程处理for (int i = 1; i <= n; i ++) {char ch1 = word1.charAt(i - 1);for (int j = 1; j <= m; j ++) {char ch2 = word2.charAt(j - 1);if (ch1 == ch2) dp[i][j] = dp[i - 1][j - 1];else dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1; } }return dp[n][m];}
}
资料获取
大家点赞、收藏、关注、评论啦~
精彩专栏推荐订阅：在下方专栏👇🏻
- 长路-文章目录汇总（算法、后端Java、前端、运维技术导航）：博主所有博客导航索引汇总
- 开源项目Studio-Vue—校园工作室管理系统(含前后台，SpringBoot+Vue)：博主个人独立项目，包含详细部署上线视频，已开源
- 学习与生活-专栏：可以了解博主的学习历程
- 算法专栏：算法收录
更多博客与资料可查看👇🏻获取联系方式👇🏻，🍅文末获取开发资源及更多资源博客获取🍅
整理者：长路 时间：2024.2.7