""
問題描述：
給定兩個單詞 word1 和 word2，計算出將 word1 轉換成 word2 所使用的最少操作數 。
你可以對一個單詞進行如下三種操作：
插入一個字符
刪除一個字符
替換一個字符
示例 1:
輸入: word1 = "horse", word2 = "ros"
輸出: 3
解釋:
horse -> rorse (將 'h' 替換為 'r')
rorse -> rose (刪除 'r')
rose -> ros (刪除 'e')
示例 2:
輸入: word1 = "intention", word2 = "execution"
輸出: 5
解釋:
intention -> inention (刪除 't')
inention -> enention (將 'i' 替換為 'e')
enention -> exention (將 'n' 替換為 'x')
exention -> exection (將 'n' 替換為 'c')
exection -> execution (插入 'u')
思路：
這道題目可以使用動態規劃來實現，通過定義一個int類型的二維數組dp，使得dp[i][j] 表示將單詞word1 中的前 i 個字符 轉換成 word2 中前j個字符所需的最少操作數。在用workd1 中第i個字符和word2中第j個字符對比過程中，會存在如下幾種情況：
1、workd1 中第i個字符和word2中第j個字符相同，此時 dp[i][j] = dp[i][j-1]
2、workd1 中第i個字符和word2中第j個字符不相同，此時 可以通過插入、刪除、替換三種操作來獲取最少的一個操作數，這三種情況如下：
2.1、插入 dp[i][j] = dp[i][j-1] + 1
2.2、刪除 dp[i][j] = dp[i-1][j] + 1
2.3、替換 dp[i][j] = dp[i-1][j-1] + 1
java代碼：
public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
dp[0][0] = 0;
for(int i = 1; i < dp[0].length; i ++){
dp[0][i] = dp[0][i - 1] + 1;
}
for(int i = 1; i < dp.length; i ++){
dp[i][0] = dp[i - 1][0] + 1;
}
for(int i = 1; i < dp.length; i ++){
for(int j = 1; j < dp[0].length; 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][j-1],dp[i-1][j]),dp[i-1][j-1]) + 1;
}
}
}
return dp[word1.length()][word2.length()];
}
相關推薦
'2019年互聯網人才招聘報告：Java吃香，算法工程師緊缺，頭條崛起'
"作者 | 八爪盒子責編 | 屠敏技術變革，人才驅動。當前互聯網的就業機會和風口在何處？在這篇文章中，我們將對 7 月份國內各個主流招聘網站發佈的384,0533 條互聯網招聘需求，其中在剔除銷售、行政等非常規互聯網職位以及非知名公司後的 7819 個在招職位進行全面分析，...
'GitHub Python項目推薦｜數據結構和算法必知必會的50個代碼實現'
"GitHub Python項目推薦|數據結構和算法必知必會的50個代碼實現項目熱度標星(star)：8860關注(watch)：486拷貝(fork)：2644貢獻人數：98 （貢獻人數很多哈）倉庫大小：1 MB最後更新：2019-08-17代碼提交活躍：開發語言主要語言...
'LeetCode算法第68題：文本左右對齊'
"問題描述：給定一個單詞數組和一個長度 maxWidth，重新排版單詞，使其成為每行恰好有 maxWidth 個字符，且左右兩端對齊的文本。你應該使用“貪心算法”來放置給定的單詞；也就是說，儘可能多地往每行中放置單詞。必要時可用空格 ' ' 填充，使得每行恰好有 maxWi...
'圖解算法第二彈：整數反轉'
"本題源自 LeetCode ，題號7。1.題目描述給出一個 32 位的有符號整數，你需要將這個整數中每位上的數字進行反轉。示例 1:輸入: 123輸出: 321示例 2:輸入: -123輸出: -321示例 3:輸入: 120輸出: 21注意:假設我們的環境只能存儲得下 ...
推薦中...