class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
//当一个字符串为空时,如果需要两个字符串都相同,必须将另一个字符串全部删除
for (int i = 1; i <= m; i++) {
dp[i][0] = i;
}
//当一个字符串为空时,如果需要两个字符串都相同,必须将另一个字符串全部删除
for (int j = 1; j <= n; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= m; i++) {
char c1 = word1.charAt(i - 1);
for (int j = 1; j <= n; j++) {
char c2 = word2.charAt(j - 1);
//如果两个字符串的字符相等,则最少删除次数不变。
if (c1 == c2) {
dp[i][j] = dp[i - 1][j - 1];
} else {
//如果两个字符串的字符不相等,则取两个字符串减一个后的最小值 然后+1。
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
}
}
}
return dp[m][n];
}
}