72/583-编辑距离

72. Edit Distance

LeetCode-72

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

method

dp[i][j]：以i-1结尾的word1和以j-1结尾的word2，要相等需要操作的步数

相等的话，dp[i][j] = dp[i-1][j-1]

不等就需要操作

1、删除

• 删除word1[i-1]，则dp[i][j] = dp[i-1][j] + 1
• 删除word2[j-1]，则dp[i][j] = dp[i][j-1] + 1

2、增加

增加word1的一个字母，相当于删除word2的一个字母，反之也是，所以递推公式和删除的是一样的

3、替换

替换word1[i-1]或word2[j-1]使其由不等变为相等，递推公式在相等的基础上增加一步操作，所以是dp[i][j] = dp[i-1][j-1] + 1

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

---

LeetCode 583. Delete Operation for Two Strings

LeetCode-583

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

Example 1:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Example 2:

Input: word1 = "leetcode", word2 = "etco"
Output: 4

method

dp[i][j]：以i-1结尾的word1，和以j-1结尾的word2，要匹配需要删除的最少步数

• word1[i-1] == word2[j-1]

相同的话步数就不变，dp[i][j] = dp[i-1][j-1]

• word1[i-1] != word2[j-1]

不同的话，分成三种情况，取最小的

1. 删除word1[i-1]，则dp[i][j] = dp[i-1][j] + 1
2. 删除word2[j-1]，则dp[i][j] = dp[i][j-1] + 1

初始化

• dp[i][0]：表示word2是空字符串，则以i-1结尾的word1要删除i个字符才能匹配
• dp[0][j]：表示word1是空字符串，则以j-1结尾的word2要删除j个字符才能匹配

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