印刷网络商城网站建设,jquery 炫酷网站,网站开发需要怎么做,上海城市建设网站代码随想录算法训练营第五十六天| 583. 两个字符串的删除操作 72. 编辑距离
一、力扣583. 两个字符串的删除操作
题目链接 思路#xff1a;相等时不删除#xff0c;不相等时#xff0c;两个字符串各删除一个#xff0c;比大小#xff0c;删除用步骤少的。
class Soluti…代码随想录算法训练营第五十六天| 583. 两个字符串的删除操作 72. 编辑距离
一、力扣583. 两个字符串的删除操作
题目链接 思路相等时不删除不相等时两个字符串各删除一个比大小删除用步骤少的。
class Solution {public int minDistance(String word1, String word2) {int[][] dp new int[word1.length()1][word2.length()1];for (int i 0; i word1.length(); i) {dp[i][0] i;}for (int i 0; i word2.length(); i) {dp[0][i] i;}for (int i 1; i word1.length(); i) {for (int j 1; j word2.length(); 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] 1, dp[i][j-1] 1);}}}return dp[word1.length()][word2.length()];}
}二、力扣72. 编辑距离
题目链接 思路区间结尾不相等有增删换dp[i][j] min({dp[i - 1][j - 1], dp[me - 1][j], dp[me][j - 1]}) 1
class Solution {public int minDistance(String word1, String word2) {int[][] dp new int[word1.length()1][word2.length()1];for (int i 0; i word1.length(); i) {dp[i][0] i;}for (int i 0; i word2.length(); i) {dp[0][i] i;}for (int i 1; i word1.length(); i) {for (int j 1; j word2.length(); 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-1], Math.min(dp[i][j-1], dp[i-1][j])) 1;}}}return dp[word1.length()][word2.length()];}
}
