组长说外包不能吃零食。。|字符串|序列|示例|算法|零食

最近一网友发文称，自己平时和组长打打闹闹的，以为组长把他当自己人，结果去拿零食的时候，组长告诉他外包不能吃零食。这都是什么鸟公司，也太离谱了，都是互联网公司，会在乎这点钱？不知道喝水会不会也不让外包的喝。

还有网友调侃，外包连厕所都不能上，只能去外面的公厕。其实外包公司是不会参加甲方公司的年会，毕竟不属于人家的员工，但零食这东西吧，我觉得真没必要防着外包，又不是啥好东西。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第583题：两个字符串的删除操作，难度是中等。

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。每步可以删除任意一个字符串中的一个字符。

示例1：

输入: word1 = "sea", word2 = "eat" 输出: 2 解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例2：

输入：word1 = "leetcode", word2 = "etco" 输出：4

1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小写英文字母

问题分析

这题说的是删除两个字符串的任意字符，并且操作的步数要最少，让剩下的字符构成的字符串相同。如果要让删除的字符最少，也就是剩下的最多，剩下的字符构成的子串也就是这两个字符串的最长公共子序列。

然后计算每一个字符串变成最长公共子序列所需要删除的字符数量，两个字符都变成最长公共子序列所需要删除的总的字符数就是这题的答案，那么这题只要能求出两个字符串的最长公共子序列长度即可。关于求两个字符串的，好多年前讲过，不懂的可以看下。

JAVA：

public int minDistance(String word1, String word2) {
    int len1 = word1.length();
    int len2 = word2.length();
    int[][] dp = newint[len1 + 1][len2 + 1];
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1))
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    // 最终结果dp[len1][len2]是最长公共子序列的长度。
    return len1 - dp[len1][len2] + len2 - dp[len1][len2];
}

C++：

public:
    int minDistance(string word1, string word2) {
        int len1 = word1.size();
        int len2 = word2.size();
        vector> dp(len1 + 1, vector(len2 + 1, 0));
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; 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[len1][len2]是最长公共子序列的长度。
        return len1 - dp[len1][len2] + len2 - dp[len1][len2];
    }

笔者简介

博哥，真名：王一博，毕业十多年，作者，专注于数据结构和算法的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解900多题，对算法题有自己独特的解题思路和解题技巧。