您好,登錄后才能下訂單哦!
這篇文章主要介紹“C++怎么編輯距離”的相關(guān)知識(shí),小編通過(guò)實(shí)際案例向大家展示操作過(guò)程,操作方法簡(jiǎn)單快捷,實(shí)用性強(qiáng),希望這篇“C++怎么編輯距離”文章能幫助大家解決問(wèn)題。
Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace "h" with "r")
rorse -> rose (remove "r")
rose -> ros (remove "e")
Example 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove "t")
inention -> enention (replace "i" with "e")
enention -> exention (replace "n" with "x")
exention -> exection (replace "n" with "c")
exection -> execution (insert "u")
這道題讓求從一個(gè)字符串轉(zhuǎn)變到另一個(gè)字符串需要的變換步驟,共有三種變換方式,插入一個(gè)字符,刪除一個(gè)字符,和替換一個(gè)字符。題目乍眼一看并不難,但是實(shí)際上卻暗藏玄機(jī),對(duì)于兩個(gè)字符串的比較,一般都會(huì)考慮一下用 HashMap 統(tǒng)計(jì)字符出現(xiàn)的頻率,但是在這道題卻不可以這么做,因?yàn)樽址捻樞蚝苤匾_€有一種比較常見(jiàn)的錯(cuò)誤,就是想當(dāng)然的認(rèn)為對(duì)于長(zhǎng)度不同的兩個(gè)字符串,長(zhǎng)度的差值都是要用插入操作,然后再對(duì)應(yīng)每位字符,不同的地方用修改操作,但是其實(shí)這樣可能會(huì)多用操作,因?yàn)閯h除操作有時(shí)同時(shí)可以達(dá)到修改的效果。比如題目中的例子1,當(dāng)把 horse 變?yōu)?rorse 之后,之后只要?jiǎng)h除第二個(gè)r,跟最后一個(gè)e,就可以變?yōu)?ros。實(shí)際上只要三步就完成了,因?yàn)閯h除了某個(gè)字母后,原來(lái)左右不相連的字母現(xiàn)在就連一起了,有可能剛好組成了需要的字符串。所以在比較的時(shí)候,要嘗試三種操作,因?yàn)檎l(shuí)也不知道當(dāng)前的操作會(huì)對(duì)后面產(chǎn)生什么樣的影響。對(duì)于當(dāng)前比較的兩個(gè)字符 word1[i] 和 word2[j],若二者相同,一切好說(shuō),直接跳到下一個(gè)位置。若不相同,有三種處理方法,首先是直接插入一個(gè) word2[j],那么 word2[j] 位置的字符就跳過(guò)了,接著比較 word1[i] 和 word2[j+1] 即可。第二個(gè)種方法是刪除,即將 word1[i] 字符直接刪掉,接著比較 word1[i+1] 和 word2[j] 即可。第三種則是將 word1[i] 修改為 word2[j],接著比較 word1[i+1] 和 word[j+1] 即可。分析到這里,就可以直接寫(xiě)出遞歸的代碼,但是很可惜會(huì) Time Limited Exceed,所以必須要優(yōu)化時(shí)間復(fù)雜度,需要去掉大量的重復(fù)計(jì)算,這里使用記憶數(shù)組 memo 來(lái)保存計(jì)算過(guò)的狀態(tài),從而可以通過(guò) OJ,注意這里的 insertCnt,deleteCnt,replaceCnt 僅僅是表示當(dāng)前對(duì)應(yīng)的位置分別采用了插入,刪除,和替換操作,整體返回的最小距離,后面位置的還是會(huì)調(diào)用遞歸返回最小的,參見(jiàn)代碼如下:
解法一:
class Solution { public: int minDistance(string word1, string word2) { int m = word1.size(), n = word2.size(); vector<vector<int>> memo(m, vector<int>(n)); return helper(word1, 0, word2, 0, memo); } int helper(string& word1, int i, string& word2, int j, vector<vector<int>>& memo) { if (i == word1.size()) return (int)word2.size() - j; if (j == word2.size()) return (int)word1.size() - i; if (memo[i][j] > 0) return memo[i][j]; int res = 0; if (word1[i] == word2[j]) { return helper(word1, i + 1, word2, j + 1, memo); } else { int insertCnt = helper(word1, i, word2, j + 1, memo); int deleteCnt = helper(word1, i + 1, word2, j, memo); int replaceCnt = helper(word1, i + 1, word2, j + 1, memo); res = min(insertCnt, min(deleteCnt, replaceCnt)) + 1; } return memo[i][j] = res; } };
根據(jù)以往的經(jīng)驗(yàn),對(duì)于字符串相關(guān)的題目且求極值的問(wèn)題,十有八九都是用動(dòng)態(tài)規(guī)劃 Dynamic Programming 來(lái)解,這道題也不例外。其實(shí)解法一的遞歸加記憶數(shù)組的方法也可以看作是 DP 的遞歸寫(xiě)法。這里需要維護(hù)一個(gè)二維的數(shù)組 dp,其大小為 mxn,m和n分別為 word1 和 word2 的長(zhǎng)度。dp[i][j] 表示從 word1 的前i個(gè)字符轉(zhuǎn)換到 word2 的前j個(gè)字符所需要的步驟。先給這個(gè)二維數(shù)組 dp 的第一行第一列賦值,這個(gè)很簡(jiǎn)單,因?yàn)榈谝恍泻偷谝涣袑?duì)應(yīng)的總有一個(gè)字符串是空串,于是轉(zhuǎn)換步驟完全是另一個(gè)字符串的長(zhǎng)度。跟以往的 DP 題目類似,難點(diǎn)還是在于找出狀態(tài)轉(zhuǎn)移方程,可以舉個(gè)例子來(lái)看,比如 word1 是 "bbc",word2 是 "abcd",可以得到 dp 數(shù)組如下:
? a b c d
? 0 1 2 3 4
b 1 1 1 2 3
b 2 2 1 2 3
c 3 3 2 1 2
通過(guò)觀察可以發(fā)現(xiàn),當(dāng) word1[i] == word2[j] 時(shí),dp[i][j] = dp[i - 1][j - 1],其他情況時(shí),dp[i][j] 是其左,左上,上的三個(gè)值中的最小值加1,其實(shí)這里的左,上,和左上,分別對(duì)應(yīng)的增加,刪除,修改操作,具體可以參見(jiàn)解法一種的講解部分,那么可以得到狀態(tài)轉(zhuǎn)移方程為:
dp[i][j] = / dp[i - 1][j - 1] if word1[i - 1] == word2[j - 1]
min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1 else
解法二:
class Solution { public: int minDistance(string word1, string word2) { int m = word1.size(), n = word2.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1)); for (int i = 0; i <= m; ++i) dp[i][0] = i; for (int i = 0; i <= n; ++i) dp[0][i] = i; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (word1[i - 1] == word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1; } } } return dp[m][n]; } };
關(guān)于“C++怎么編輯距離”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí),可以關(guān)注億速云行業(yè)資訊頻道,小編每天都會(huì)為大家更新不同的知識(shí)點(diǎn)。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。