583. 兩個字符串的刪除操作

題目描述

給定兩個單詞 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步數(shù)。
每步 可以刪除任意一個字符串中的一個字符。
示例1：
輸入：$word1="sea",word2="eat"$
輸出：$2$
示例2：
輸入：$word1="leetcode",word2="etco"$
輸出：$4$

思路

1、確定dp數(shù)組
dp[i][j]表示以i-1為結尾的字符串word1和以j-1為結尾的字符串word2，想要達到相等，所需要刪除元素的最少次數(shù)
2、確定遞推公式
當word[i-1]和word2[j-1]相等時，直接等于上一狀態(tài)即可
不相等時，存在三種情況：
1）刪word1[i-1]
2）刪word2[j-1]
3）同時刪word1[i-1]和word2[j-1]
最后取最小值

解法

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 = 1;i<= len1;i++){for(int j = 1;j<=len2;j++){if(word1.charAt(i-1) == word2.charAt(j-1)){dp[i][j] = dp[i-1][j-1] +1;}else{dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}}return len1+len2-dp[len1][len2]*2;}
}

總結

好好看，好好學

72. 編輯距離

題目描述

給你兩個單詞 word1 和 word2， 請返回將 word1 轉換成 word2 所使用的最少操作數(shù) 。
你可以對一個單詞進行如下三種操作：
插入一個字符
刪除一個字符
替換一個字符
示例1：
輸入：$word1="horse",word2="ros"$
輸出：$3$
示例2：
輸入：$word1="intention",word2="execution"$
輸出：$5$

思路

1、確定dp數(shù)組
dp[i][j]表示以下標i-1為結尾的字符串word1，和以下標j-1為結尾的字符串word2，最近編輯距離為dp[i][j]
2、確定遞推公式
word1[i-1]和word2[j-1]
相等時，不進行操作
不相等時，可以進行增刪改的動作

解法

class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int 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++){for(int j = 1;j<=n;j++){if(word1.charAt(i-1) == word2.charAt(j-1)){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j])+1;}}}return dp[m][n];}
}

總結

最近考試周，沒細看，我有罪，等考試周結束之后再好好總結