题目描述
给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
示例：
输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
思路分析
这道题给我们两个字符串，要求删除最少次数，使得最后剩下的两个字符串相同。也就是说，这道题要求我们尽可能多的保留相同的字符串，才能使删除的次数最少。这道题就是我们上一次所求的 “最长公共子序列” 的变种，详细可以点击这里：最长公共子序列，获得最长公共子序列长度后，只要把 word1 的长度减最长最长公共子序列长度及 word2 的长度减去最长公共子序列长度的结果求和，就能得到最少删除次数。
代码描述
使用 Java 进行代码描述：
class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
int dp[][] = new int[len1 + 1][len2 + 1];
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
if (word1.charAt(i) == word2.charAt(j)) {
dp[i + 1][j + 1] = dp[i][j] + 1;
} else {
dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
}
}
}
int deleteNum = dp[len1][len2];
return len1 + len2 - 2 * deleteNum ;
}
}
