Leetcode DAY 56: 两个字符串的删除操作 and 编辑距离

• 583. 两个字符串的删除操作

1 、 dp[i][j]  表示  让以word1[i - 1]为结尾的字符串 和 以word2[i - 2]为结尾的字符串 相等需要删除的最少次数

1、dp[i][j] 的 递推需要考虑两种情况：

（1）word1[i - 1] == word2[j - 1]   相当于不考虑word1[i]和word2[j] 只考虑前面的  所以dp[i][j] = dp[i - 1][j - 1]

（2）word1[i - 1] != word2[j - 1]  ；如果不考虑word1[i - 1] 那么dp[i][j] = dp[i - 1][j] + 1; 如果不考虑word2[j - 1]  那么dp[i][j] = dp[i][j - 1] + 1 ; 如果都不考虑   那么dp[i][j] = dp[i - 1][j - 1] + 2

class Solution {
public:int minDistance(string word1, string word2) {int n = word1.size();int m = word2.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1));//dp[0][j]   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++) {for(int j = 1; j <= m; j++) {if(word1[i - 1] == word2[j - 1]) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);}}}return dp[n][m];}
};

• 72. 编辑距离

1、dp[i][j]表示  以word1[i - 1]为结尾的字符串  -> 以word2[j - 1]为结尾的字符串需要的最少操作次数

2、 word1[i - 1] & word2[j - 1]相等   ->不操作  dp = dp[i -1][j - 1]

     不相等 可以进行 （增 删 换） 

   （1）增： 相当于 不考虑word2[j - 1]  操作数 + 1   

     (2)  删 ：相当于  不考虑word2[i -1]   操作数 + 1

     (3)  换：相当于 把word1[i - 1] 替换成word2[j - 1]  相当于 不考虑这俩  操作数 + 1

class Solution {
public:int minDistance(string word1, string word2) {int n = word1.size();int m = word2.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1));// dp[i][0]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++) {for(int j = 1; j <= m; j++) {if(word1[i - 1] == word2[j - 1]) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1));}}}return dp[n][m];}
};