文章目錄
- 😉毛遂自薦
- ?題目
- 第一個思路：最長公共子序列
- 代碼實作
- 第二種：正經點DP
- 代碼實作
- 💖最后
Code皮皮蝦 一個沙雕而又有趣的憨憨少年，和大多數小伙伴們一樣喜歡聽歌、游戲，當然除此之外還有寫作的興趣，emm…，日子還很長，讓我們一起加油努力叭🌈
👉話不多說，直達底部有粉絲專享福利！！！
😉毛遂自薦
毛遂自薦一下，給大家推薦一下自己的專欄😁，歡迎小伙伴們收藏關注😊
大廠面試題專欄
Java專欄
爬蟲專欄
力扣刷題專欄
更多專欄盡在主頁，點我😁！！！
?題目
相信老司機一看就知道要用動態規劃，哈哈哈，做的太多啦😂
第一個思路：最長公共子序列
題目說：找到使得 word1 和 word2 相同所需的最小步數，那我們找word1和word2的最長公共子序列，得到它的長度，再分別用word1和word2的長度減去最長公共子序列，就得到最少步數，
代碼實作
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
char tmp1 = ' ', tmp2 = ' ';
for (int i = 1; i <= m; i++) {
tmp1 = word1.charAt(i - 1);
for (int j = 1; j <= n; j++) {
tmp2 = word2.charAt(j - 1);
if (tmp1 == tmp2) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
int max = dp[m][n];
return m - max + n - max;
}
}
第二種：正經點DP
定義dp[i][j] 為 word1前i個字符，word2前j個字符所需的最小步數
- 當
word1.charAt(i - 1) == word2.charAt(j - 1)，那么不用洗掉，則dp[i][j] = dp[i - 1][j - 1]; - 當
word1.charAt(i - 1) != word2.charAt(j - 1)，那么要洗掉一個，當然要選擇最優的刪，則dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
代碼實作
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;
}
char tmp1 = ' ',tmp2 = ' ';
for (int i = 1; i <= m; i++) {
tmp1 = word1.charAt(i - 1);
for (int j = 1; j <= n; j++) {
tmp2 = word2.charAt(j - 1);
if (tmp1 == tmp2) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
}
}
}
return dp[m][n];
}
}
💖最后
我是 Code皮皮蝦，一個熱愛分享知識的 皮皮蝦愛好者，未來的日子里會不斷更新出對大家有益的博文，期待大家的關注！！！
創作不易，如果這篇博文對各位有幫助，希望各位小伙伴可以一鍵三連哦！，感謝支持，我們下次再見~~~
公眾號干貨內容輸出，囊括Java、Python爬蟲、力扣題解、大廠面試題 四大系列，更有長時間總結的干貨資源分享，后臺回復：面試資料即可領取
最后，祝各位步步高升🚀🚀🚀
粉絲福利👇🏻👇🏻👇🏻
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/303924.html
標籤：其他
上一篇：美圖秀秀和網頁美工的合作