?LeetCode刷題實(shí)戰(zhàn)583：兩個(gè)字符串的刪除操作
Given?two?strings?word1?and?word2,?return?the?minimum?number?of?steps?required?to?make?word1?and?word2?the?same.
In?one?step,?you?can?delete?exactly?one?character?in?either?string.
示例
示例 1：
輸入: word1 = "sea", word2 = "eat"
輸出: 2
解釋: 第一步將 "sea"?變?yōu)?"ea"?，第二步將 "eat "變?yōu)?"ea"
示例 ?2:
輸入：word1 = "leetcode", word2 = "etco"
輸出：4
解題
主要思路：動態(tài)規(guī)劃
class?Solution?{
????public?int?minDistance(String word1, String word2)?{
????????int?m = word1.length(), n = word2.length();
????????int[][] dp = new?int[m + 1][n + 1];
????????//當(dāng)一個(gè)字符串為空時(shí)，如果需要兩個(gè)字符串都相同，必須將另一個(gè)字符串全部刪除
????????for?(int?i = 1; i <= m; i++) {
????????????dp[i][0] = i;
????????}
????????//當(dāng)一個(gè)字符串為空時(shí)，如果需要兩個(gè)字符串都相同，必須將另一個(gè)字符串全部刪除
????????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);
????????????????//如果兩個(gè)字符串的字符相等，則最少刪除次數(shù)不變。
????????????????if?(c1 == c2) {
????????????????????dp[i][j] = dp[i - 1][j - 1];
????????????????} else?{
????????????????????//如果兩個(gè)字符串的字符不相等，則取兩個(gè)字符串減一個(gè)后的最小值 然后+1。
????????????????????dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
????????????????}
????????????}
????????}
????????return?dp[m][n];
????}
}