给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
示例：
输入: “sea”, “eat” 输出: 2 解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
解法1： 动态规划 链接：https://leetcode-cn.com/problems/delete-operation-for-two-strings/solution/liang-chong-jie-fa-by-jason-2-34/
int minDistance(string word1, string word2) { const int len1 = word1.size(); const int len2 = word2.size(); vector<vector<int>> d(len1+1,vector<int>(len2+1,0)); for(int i=0;i<=len1;++i){ for(int j=0;j<=len2;++j){ if(i == 0 && j == 0){ d[i][j] = 0; }else if(i == 0 && j){ d[i][j] = j; }else if(i && j == 0){ d[i][j] = i; }else{ d[i][j] = min( min(d[i-1][j],d[i][j-1])+1, d[i-1][j-1] + (word1[i-1] == word2[j-1] ? 0 :2) ); } } } return d[len1][len2]; }解法2： 最长公共字串 链接：https://leetcode-cn.com/problems/delete-operation-for-two-strings/solution/liang-chong-jie-fa-by-jason-2-34/
int minDistance(string word1, string word2) { const int len1 = word1.size(); const int len2 = word2.size(); vector<vector<int>> d(len1+1,vector<int>(len2+1,0)); for(int i=0;i<=len1;++i){ for(int j=0;j<=len2;++j){ if(i == 0 || j == 0){ d[i][j] = 0; }else{ if(word1[i-1] == word2[j-1]) { d[i][j] = d[i-1][j-1] + 1; }else d[i][j] = max(d[i-1][j],d[i][j-1]); } } } return len1+len2-2*d[len1][len2]; }