思路：本题要求使得 word1 和 word2 相同所需要删除的最小字符数，也就是说要找到最大的公共子串需要删除多少个字符，那么本题依旧可以延续之前的思路，不同的地方在于本题是两个字符串都可以删，也就是在推导条件的时候需要做出变化，其他基本思路相同。
我们设 dp[i][j]表示以word1[i-1]结尾字符串和word2[j-1]结尾的字符串想要达到相等要删去的次数。那么我们需要初始化所有的dp[i][0]和dp[0][j],以word1[i-1]结尾字符串和字
符串0想要达到相等要删去的次数很明显为字符串长度本身，所以初始化如下：
for (int i = 0; i < word1.length() + 1;i++){
dp[i][0] = i;
}
for (int j = 0; j < word2.length() + 1;j++){
dp[0][j] = j;
}
在遍历中我们同样以word1.charAt(i-1) == word2.charAt(j-1),作为判断条件来进行dp数组的推导，当相等的时候，我们没必要进行删除，直接继承两个字符串上一位的dp值即可。当不相等的时候，我们需要进行删除，这里考虑的情况就比较多，我们可以删去任意一个字符串的字符，dp[i-1][j]+1或者dp[i][j-1]+1,或者两个字符串都进行删除dp[i-1][j-1]+2，从中选一个最小的即可
class Solution {
public int minDistance(String word1, String word2) {
// dp[i][j]表示以word1[i-1]结尾字符串和word2[j-1]结尾的字符串想要达到相等要删去的次数
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
for (int i = 0; i < word1.length() + 1;i++){
dp[i][0] = i;
}
for (int j = 0; j < word2.length() + 1;j++){
dp[0][j] = j;
}
for (int i = 1; i < word1.length()+1; i++) {
for (int j = 1; j < word2.length() + 1 ; j++) {
if (word1.charAt(i-1) == word2.charAt(j-1)){
// 不用删直接继承两边上一位的dp即可
dp[i][j] = dp[i-1][j-1];
}else {
// 两边都可以删,或者只删一边(只是在逻辑上删去)
dp[i][j] = Math.min(dp[i-1][j]+1,Math.min(dp[i][j-1]+1,dp[i-1][j-1]+2));
}
}
}
return dp[word1.length()][word2.length()];
}
}
