leetcode C++11題解系列-071 編輯距離

2020-08-06 第一路痴索隆
leetcode C++11題解系列-071 編輯距離

題目

給你兩個單詞 word1 和 word2，請你計算出將 word1 轉換成 word2 所使用的最少操作數 。

你可以對一個單詞進行如下三種操作：

插入一個字符
刪除一個字符
替換一個字符
 

示例 1：

輸入：word1 = &34;, word2 = &34;
輸出：3
解釋：
horse -> rorse (將 &39; 替換為 &39;)
rorse -> rose (刪除 &39;)
rose -> ros (刪除 &39;)
示例 2：

輸入：word1 = &34;, word2 = &34;
輸出：5
解釋：
intention -> inention (刪除 &39;)
inention -> enention (將 &39; 替換為 &39;)
enention -> exention (將 &39; 替換為 &39;)
exention -> exection (將 &39; 替換為 &39;)
exection -> execution (插入 &39;)

解題代碼與測試

//
// Created by tannzh on 2020/8/5.
//

/*
*
* 編輯距離
給你兩個單詞 word1 和 word2，請你計算出將 word1 轉換成 word2 所使用的最少操作數 。

你可以對一個單詞進行如下三種操作：

插入一個字符
刪除一個字符
替換一個字符
 

示例 1：

輸入：word1 = &34;, word2 = &34;
輸出：3
解釋：
horse -> rorse (將 &39; 替換為 &39;)
rorse -> rose (刪除 &39;)
rose -> ros (刪除 &39;)
示例 2：

輸入：word1 = &34;, word2 = &34;
輸出：5
解釋：
intention -> inention (刪除 &39;)
inention -> enention (將 &39; 替換為 &39;)
enention -> exention (將 &39; 替換為 &39;)
exention -> exection (將 &39; 替換為 &39;)
exection -> execution (插入 &39;)

*/

include <string>
34;intention&34;execution&34;矩陣"的方式，來積累每一次的子問題結果的手段，是非常非常明顯的** DP (動態規劃問題) ** 。 想一想 [29. Unique Paths](../29. Unique Paths)，再想想楊輝三角，就會發現其本質完全一致。

由於 DP 問題，十分依賴上一次的結果，而對於 nm 的解空間矩陣來說，首行與首列，是無法通過 DP 手段計算出的，若仍想要依賴 DP。我們需要在外面手工包一層。即讓整個解空間矩陣(nm)都有上一次的結果可依。

那麼就成了一個 (n+1) * (m+1) 的矩陣了。

對於首行，即 i 不變， j 遞增，即：

|
|gggg ...

顯然屬於[定理3]的範疇，可知第一行為：{0, 1, 2, 3 ...}

同理，對於首列，即 j 不變， i 遞增，即：

|gggg ...
|

顯然屬於[定理2]的範疇，可知第一列為：{0, 1, 2, 3 ...}

最終矩陣的外殼，看起來就是：

_ _
|0 1 2 3 4 5 ... |
|1
|2
|3
|4
|5
|.
|.
|_ _ |

而我們需要做的，便是填充這個矩陣，問題的最終解是該矩陣右下角的值：A[n][m].

相關焦點

  • Leetcode題解 WordBreak
    題解算法及複雜度（6 ms）  本問題是確定一個字符串是否能分割成多個單詞，這些單詞都在字典中出現.  由於本題每個組成成分都是單詞，也就是每次在原有字符串的返回true的基礎上增加一個字典中的單詞來組成新的能夠返回true的字符串.發現這是一種全局同一限制性的求解問題，限制條件是每次字符串增加的都是一個存在於字典中的單詞.舉個例子說明一下:  比如字符串是"leetcodeisnice
  • ​LeetCode刷題實戰72:編輯距離
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 編輯距離，我們先來看題面：https://leetcode-cn.com/problems/edit-distanceGiven two words word1 and word2, find the minimum number of operations required to convert word1
  • ​LeetCode刷題實戰161:相隔為1的編輯距離
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 相隔為 1 的編輯距離  ，我們先來看題面：https://leetcode-cn.com/problems/one-edit-distance/Given two strings S and T, determine if they are both one edit distance apart.
  • ​LeetCode刷題實戰18: 四數之和
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做四數之和 ，我們先來看題面：https://leetcode-cn.com/problems/4sum/Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such
  • LeetCode-72.編輯距離(Edit Distance)
    編輯距離給你兩個單詞 word1 和 word2，請你計算出將 word1 轉換成 word2 所使用的最少操作數 。(刪除 't')inention -> enention (將 'i' 替換為 'e')enention -> exention (將 'n' 替換為 'x')exention -> exection (將 'n' 替換為 'c')exection -> execution (插入 'u')來源：力扣（LeetCode）連結：https://leetcode-cn.com
  • LeetCode 刷題指南(1):為什麼要刷題
    ，不過不可否認刷題確實能鍛鍊我們的編程能力，相信每個認真刷題的人都會有體會。類似的題目也許有類似的結構，類似的性質，類似的解方案。通過考察或回憶一個類似的題目是如何解決的，也許就能夠借用一些重要的點子（比較 Ugly Number 的三個題目：263. Ugly Number， 264. Ugly Number II， 313. Super Ugly Number）。用特例啟發思考。通過考慮一個合適的特例，可以方便我們快速尋找出一般問題的解。
  • C++學習方法之——LeetCode刷題
    為什麼要選擇刷題呢，基本上所有的程式設計師的崗位招聘時，先筆試再面試，筆試是什麼，就是這些題。程序語言，和我們練習英語和其他外語一樣很類似，只有通過大量的練習才能熟能生巧。網站上給的算法類的題庫英文界面目前是937道，還是需要很久才能慢慢啃完的。
  • leetcode刷題指南之PalindromePairs
    則(0, 1)為一解；對於"bat", 我們發現map["tab"] = 0，且末尾串""為回文串。則(1, 0)為一解。故答案為[[0, 1], [1, 0]]。if(i < a.size()&&j >= 0) return false; 7    if(j < 0){ 8        j = a.size()-1; 9        while(i < j&&a[i] == a[j]) i++, j--;10        return i >= j;11
  • 【SQL刷題系列】:leetcode180 Consecutive Numbers
    點擊上方 ↑ 藍色關注「Python數據科學」SQL刷題系列：SQL作為一種資料庫查詢和程序設計語言，是從事數據技術人員必備的技能，也是各大公司的數據分析、數據挖掘、資料庫等筆試題必考的一種題。為此，Python數據科學開啟了SQL刷題的系列，希望可以幫助有需要的朋友們。
  • LeetCode 刷題指南(一):為什麼要刷題
    作者：數據結構與算法原文連結：selfboot.cn/2016/07/24/leetcode_guide_why/前言雖然刷題一直飽受詬病，不過不可否認刷題確實能鍛鍊我們的編程能力
  • ​LeetCode刷題實戰11: 盛最多水的容器
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！隔板之間的距離為1，當下要從n個隔板當中選出兩個，在其中注水，並且要使得容納的水儘量多。請問最多能容納多少水？可以忽略隔板的寬度，將水庫看成是正規的長方體。
  • C#刷遍Leetcode面試題系列連載(2): No.38 - 報數
    前言前文傳送門：C# 刷遍 Leetcode 面試題系列連載
  • Google C++項目編程風格指南 (中文版) 分享
    源GitHub項目：https://github.com/google/styleguide中文翻譯：https://github.com/zh-google-styleguide/zh-google-styleguide如果下載有問題，可以在後臺回覆：「c++
  • leetcode刷題最強指南(版本1.0)
    為什麼會有這篇刷題指南很多剛開始刷題的同學都有一個困惑：面對leetcode上近兩千道題目，從何刷起
  • leetcode刷題指南之PatchingArray
    > 5    long long sum = 0; 6    while(sum < n){ 7        if(i < nums.size()&&nums[i] <= sum+1) 8            sum += nums[i++]; 9        else{10            ans++;11
  • Leetcode題解 HouseRobber
    題意題解算法及複雜度（Run Time 0ms）這個一個求最優解的問題因為動態規劃常用來求最優解。先假定這個問題可以用動態規划進行求解，找最優子結構，假定求前n+1(n >= 2 )個房屋盜賊能偷到的最多的錢為dp[n]。由於每個房屋的錢都是非負的，所以前n+1個房屋的總的可以偷的錢，要麼與前n個房屋偷的錢相等，要麼等於前n-1個房屋可以偷的錢，加上第n+1個房屋的錢數，除了這兩種情況外，沒有其他情況。
  • Leetcode刷題-動態規劃
    整體代碼結構也是與第五題的動態規劃代碼類似。編輯距離 題目描述：給你兩個單詞 word1 和 word2，請你計算出將 word1 轉換成 word2 所使用的最少操作數 。inention (刪除 't')inention -> enention (將 'i' 替換為 'e')enention -> exention (將 'n' 替換為 'x')exention -> exection (將 'n' 替換為 'c')exection -> execution (插入 'u')思路：第一次接觸編輯距離這樣的問題
  • 回溯法|一文解決四道 Leetcode「組合總和」題
    解集不能包含重複的組合。解集不能包含重複的組合。 組合總和」 和 「leetcode-40.1.2 題目分析當我們遇到：「可行解是什麼、可行解有多少個」這類問題時，最樸素的想法就是「枚舉」，枚舉出所有可能的結果，並在枚舉的過程中不斷刪除不符合條件的解。
  • LeetCode 系列 第5題
    複習了一下第5題， 這篇文章Review一下思路和代碼P0005
  • 【SQL刷題系列】:leetcode183 Customers Who Never Order
    （點擊上方藍色，快速關注）SQL刷題系列：SQL作為一種資料庫查詢和程序設計語言，是從事數據技術人員必備的技能