583. Delete Operation for Two Strings

Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.

Example 1:

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

Note:

1. The length of given words won't exceed 500.

2. Characters in given words can only be lower-case letters.

可以先找到longest common subsequence長度之後再分別用兩個string長度和LCS長度的差，來得到答案。word1長度和LCS長度的差是word1需要刪減的距離，word2長度和LCS長度的差是word2需要刪減的距離，兩個差相加就是所求。 dp[i][j]代表的就是word1[0...i - 1]和word2[0...j - 1]的LCS的長度。 dp state transition: dp[i][j] = dp[i - 1][j - 1] + 1 if word1[i - 1] == word2[j - 1] dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) if word1[i - 1] != word2[j - 1]

// Dynamic Programming
int minDistance(string word1, string word2) { // time: O(m * n); space: O(m * n)
    if (word1.empty()) return word2.length();
    if (word2.empty()) return word1.length();
    int m = word1.length(), n = word2.length();
    vector<vector<int> > dp(m + 1, vector<int> (n + 1, 0));
    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] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    // dp[m][n]: the length of LCS 
    return (m - dp[m][n]) + (n - dp[m][n]);
}

dp[i][j]的意義和第一個解法的dp table不一樣，這裡指的是把word1[0...i - 1]和word2[0...j - 1]刪減成一樣需要的操作次數。 dp state transition: dp[i][j] = dp[i - 1][j - 1] if word1[i - 1] == word2[j - 1] dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1 if word1[i - 1] == word2[j - 1]

// Dynamic Programming Similar to Edit Distance
int minDistance(string word1, string word2) { // time: O(m * n); space: O(m * n)
    if (word1.empty()) return word2.length();
    if (word2.empty()) return word1.length();
    int m = word1.length(), n = word2.length();
    vector<vector<int> > dp(m + 1, vector<int> (n + 1, 0));
    for (int j = 1; j <= n; ++j) dp[0][j] = j;
    for (int i = 1; i <= m; ++i) {
        dp[i][0] = 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] + 1, dp[i][j - 1] + 1);
            }
        }
    }
    return dp[m][n];
}