583.md

583. Delete Operation for Two Strings

Leetcode link

解题思路

本题给定我们两个字符串，要求删除最少的字符使得两个字符串相同

本题考虑动态规划的思考

我们需要一个二维数组 dp，其中 dp[i][j] 表示使 word1 长度为 i 的前缀与 word2 长度为 j 的前缀相同的最少删除操作次数

首先判断边界情况：

• i = 0：表示 word1 字符串为空，那么对于任意的 j，有 dp[0][j] = j
• j = 0：表示 word2 字符串为空，呢么对于任意的 i，有 dp[i][0] = i

再来判断 i，j 都大于 0 的情况

• word1[i - 1] = word2[j - 1]：加入两个相同的字符，则他们的最少删除数取决于之前的删除个数，换言之 dp[i][j] = dp[i-1][j-1]
• word1[i - 1] != word2[j - 1]：加入两个不相同的字符，这个时候要判断 dp[i][j - 1] 还是dp[i - 1][j] 哪个比较小，将比较小的那个 +1

综上所述，状态转移方程为：

$$dp[i][j] = \left{ \begin{array}{ll} dp[i - 1][j - 1] & & word1[i - 1] = word2[j - 1] \\ min(dp[i - 1][j], dp[i][j - 1]) & & word1[i - 1] \neq word2[j - 1] \end{array} \right.$$

C++

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.size();
        int len2 = word2.size();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1));
        for(int i = 1;i <= len1;i++) {
            dp[i][0] = i;
        }
        for(int j = 1;j <= len2;j++) {
            dp[0][j] = j;
        }
        
        for(int i = 1;i <= len1;i++) {
            char c1 = word1[i-1];
            for(int j = 1;j <= len2;j++) {
                char c2 = word2[j-1];
                if(c1 == c2) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;
                }
            }
        }
        return dp[len1][len2];
    }
};

Javascript

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    let len1 = word1.length;
    let len2 = word2.length;
    let dp = new Array(len1+1).fill(0).map(_=>_ = new Array(len2+1).fill(0));
    for(let i = 1;i <= len1;i++) {
        dp[i][0] = i;
    }
    for(let j = 1;j<=len2;j++) {
        dp[0][j] = j;
    }
    
    for(let i = 1;i <= len1;i++) {
        let c1 = word1[i - 1];
        for(let j = 1;j <= len2;j++) {
            let c2 = word2[j - 1];
            if(c1 === c2) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + 1;
            }
        }
    }
    return dp[len1][len2];
};