Given two words word1 and word2, find the minimum number of steps required to make word1 and word2the same, where each step deletes one character from either string.

Example:

Input: "sea", "eat"
Output: 2
Explanation: In the first step, change "sea" to "ea"; in the second step, change "eat" to "ea"

Constraints:

1. The length of each given word does not exceed 500.
2. The characters in each given word are lowercase English letters.

Approach

#

Problems involving two strings and an edit-distance-like operation are generally straightforward to solve with two-dimensional dynamic programming.

There are two ways to think about this problem, both using dynamic programming: a forward perspective and a backward perspective.

Forward Perspective

#

dp[i][j] represents the answer: the minimum number of deletion operations needed for the string formed by the first i characters of word1 and the first j characters of word2.

The boundary conditions are dp[i][0]=i(i <= word1.length) and dp[0][i]=i(i <= word2.length). An empty string and a string of length i can only become equal by deleting all i characters from the non-empty string, so the boundary conditions follow directly.

The dynamic-programming transitions are:

• dp[i + 1][j + 1] = dp[i][j] (a[i] == b[j])
• dp[i + 1][j + 1] = min(dp[i + 1][j], dp[i][j + 1]) + 1 (a[i] != b[i])

In the first case, when the two characters are equal, the deletion distance does not increase.

The second case is also easy to understand. If the current characters cannot be matched, we must delete one character and then continue comparing, so we take the smaller value and add 1.

Backward Perspective

#

Since the operation deletes some characters from the strings, what should we call the common part that remains? On closer inspection, it is the longest common subsequence.

We can first find the length of the longest common subsequence of the two strings, then subtract twice that length from the sum of the two string lengths. The result is the total number of characters that must be removed from both strings.

The boundary conditions are dp[i][0]=0 and dp[0][i]=0.

The dynamic-programming transitions are:

• dp[i + 1][j + 1] = dp[i][j] + 1 (a[i] == b[j])
• dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]) (a[i] != b[i])

These transitions are also straightforward to understand.

C++ Code (Forward)

#

#define REP(i, j) for (int i = 0; i < j; ++i)
class Solution {
public:
    int minDistance(string a, string b) {
        int m = a.size(), n = b.size();
        int dp[m + 1][n + 1];
        memset(dp, 0, sizeof dp);
        REP(i, m) REP(j, n)
            if (a[i] == b[j]) dp[i + 1][j + 1] = dp[i][j] + 1;
            else dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
        return m + n - 2 * dp[m][n];
    }
};

C++ Code (Backward)

#

#define REP(i, j) for (int i = 0; i < j; ++i)
class Solution {
public:
    int minDistance(string a, string b) {
        /*这破烂玩意不用dp做我把力扣炸了*/
        int m = a.size(), n = b.size();
        int dp[m + 1][n + 1];
        memset(dp, 0, sizeof dp);
        REP(i, m) REP(j, n)
            if (a[i] == b[j]) dp[i + 1][j + 1] = dp[i][j] + 1;
            else dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
        return m + n - 2 * dp[m][n];
    }
};