本文主要是介绍代码随想录二刷day56,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
- 前言
- 一、力扣583. 两个字符串的删除操作
- 二、力扣72. 编辑距离
前言
一、力扣583. 两个字符串的删除操作
class Solution {public int minDistance(String word1, String word2) {int row = word1.length()+1;int col = word2.length()+1;int[][] dp = new int[row][col];for(int i = 0; i < row; i ++){dp[i][0] = i;}for(int j = 0; j < col; j ++){dp[0][j] = j;}for(int i = 1;i < row; i ++){for(int j = 1; j < col; j ++){if(word1.charAt(i-1) == word2.charAt(j-1)){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+1;}}}return dp[row-1][col-1];}
}
二、力扣72. 编辑距离
class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m + 1][n + 1];// 初始化for (int i = 1; i <= m; i++) {dp[i][0] = i;}for (int j = 1; j <= n; j++) {dp[0][j] = j;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// 因为dp数组有效位从1开始// 所以当前遍历到的字符串的位置为i-1 | j-1if (word1.charAt(i - 1) == word2.charAt(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]), dp[i - 1][j]) + 1;}}}return dp[m][n];}
}
这篇关于代码随想录二刷day56的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!