题目

给定两个单词 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 只包含小写英文字母

  解题方法

  动态规划（最长子序列）

  设两个字符串长度分别为n1和n2，求解删除字符的最小个数，即求解最长公共子序列的长度n，分别将两个字符串中多余部分删除。因此删除字符的最小个数为(n1+n2-2×n)。
  求解最长公共子序列长度使用动态规划的方法，设定动态数组dp[i][j]描述word1[0, i-1]与word2[0, j-1]的最长公共子序列长度，则有如下递推关系：
  
  时间复杂度O(mn)，空间复杂度O(min(m, n))。
  C++代码：

  class Solution {
  public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size();
        int n2 = word2.size();
        vector<int> dp(n2+1, 0);
        for(int i=1; i<=n1; i++) {
            for(int j=1, pre=dp[0]; j<=n2; j++) {
                int t = dp[j];
                if(word1[i-1]==word2[j-1])  dp[j] = pre+1;
                else dp[j] = max(dp[j], dp[j-1]);
                pre = t;
            }
        }
  
        return (n1+n2-2*dp[n2]);
    }
  };
  

  动态规划

  设定动态数组dp[i][j]表示为使字符串word1[0, i-1]和word2[0, j-1]相同需要删除元素的最小个数。则对于dp[0][j]需要将word2中对应元素全部删除才能够形成空字符，所以dp[0][j] = j；同理，有dp[i][0] = i。其余元素递推关系如下：
  
  将其压缩至一维后时间复杂度为O(mn)，空间复杂度O(min(m, n))。
  C++代码：

  class Solution {
  public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size();
        int n2 = word2.size();
        vector<int> dp(n2+1, 0);
        for(int i=1; i<=n2; i++)    dp[i] = i;
        for(int i=1; i<=n1; i++) {
            int pre=dp[0];
            dp[0] = i;
            for(int j=1; j<=n2; j++) {
                int t = dp[j];
                if(word1[i-1]==word2[j-1])  dp[j] = pre;
                else dp[j] = min(dp[j]+1, dp[j-1]+1);
                pre = t;
            }
        }
  
        return dp[n2];
    }
  };