两个字符串的删除操作

动态规划1

1. 数组含义: 以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数

2. 递推公式:

   1. 当两个不相等(有三种情况)

      1. 删word[i-1], 操作次数为dp[i-1][j] + 1
      2. 删word[j-1], 操作次数为dp[i][j-1] + 1
      3. 同时删两个, 操作次数为dp[i-1][j-1] + 2 (dp[i-1][j-1] + 1等于上面either, 可忽略)

      (最后当然是取最小值)

3. 初始化: 当一个字符串是空的时, 需要几步才能变成相同的呢, 答案是i或者j

class Solution {public int minDistance(String word1, String word2) {//动规一, 通过取删除操作的最小值int len1 = word1.length();int len2 = word2.length();int[][] dp = new int[len1 + 1][len2 + 2];//初始化, 都是i//这里是<=, 因为要让数组正好等于string长度for(int i = 0; i <= len1; i++){dp[i][0] = i;}for(int j = 0; j <= len2; j++){dp[0][j] = j;}//开始遍历for(int i = 1; i <= len1; i++){for(int j = 1; j <= len2; j++){//如果相等的话又不用操作if(word1.charAt(i - 1) == word2.charAt(j - 1)){dp[i][j] = dp[i - 1][j - 1];} else {//不相等, 要么删i要么删j, 最小值dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);}}}return dp[len1][len2];}
}

动态规划2:

本题基础上和LC1143(最长公共子序列)是有点相似的, 只需要算出总共相同的字母长度, 然后全部的减去这个值就行了

class Solution {public int minDistance(String word1, String word2) {int len1 = word1.length();int len2 = word2.length();int[][] dp = new int[len1 + 1][len2 + 1];//这个版本的话先求最长公共子序列, 初始值必然是0for(int i = 1; i <= len1; i++){for(int j = 1; j <= len2; j++){if(word1.charAt(i-1) == word2.charAt(j-1)){//如果相等长度就加一dp[i][j] = dp[i-1][j-1] + 1;} else {//否则分别退一步,看哪个大dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);}}}//最后算出来的是长度, 所以两个加起来减去长度*2return len1 + len2 - dp[len1][len2]*2;}
}

编辑字符

给你两个word, 请计算出将word1转换成word2所使用的最小操作数(上一题只需要删除, 这里可以进行插入, 删除, 和替换)

仍然还是经典五部曲:

1. 数组定义: 以i-1和j-1为结尾的数据,最近编辑距离为dp[i][j]
2. 递推公式: 有四种操作: 不操作,增, 删, 改
   1. 如果word相等, 说明不用编辑, 那么就是dp[i-1][j-1]
   2. 如果不相等, 此时就要编辑栏
      1. 删除: word1或者word2删除一个元素, 次数加一: dp[i][j-1]+1/dp[i-1][j]+1
      2. 增加: 其实可以发现, 增加一个元素就是相当于另一个word减少一个元素
      3. 替换: 可以理解为两个都退一步, dp[i-1][j-1] + 1
3. 初始化: 这里和上一题一样 ,默认为i

class Solution {public int minDistance(String word1, String word2) {int len1 = word1.length();int len2 = word2.length();int[][] dp = new int[len1 + 1][len2 + 1];for(int i = 0; i <= len1; i++){dp[i][0] = i;}for(int j = 0; j <= len2; j++){dp[0][j] = j;}for(int i = 1; i <= len1; i++){for(int j = 1; j <= len2; j++){if(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] + 1),dp[i-1][j-1] + 1);}}}return dp[len1][len2];}
}