這篇文章主要介紹“C++怎么編輯距離”的相關(guān)知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強(qiáng)，希望這篇“C++怎么編輯距離”文章能幫助大家解決問題。
大田網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián)公司,大田網(wǎng)站設(shè)計制作，有大型網(wǎng)站制作公司豐富經(jīng)驗。已為大田上千提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)營銷網(wǎng)站建設(shè)要多少錢，請找那個售后服務(wù)好的大田做網(wǎng)站的公司定做！
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")
這道題讓求從一個字符串轉(zhuǎn)變到另一個字符串需要的變換步驟，共有三種變換方式，插入一個字符，刪除一個字符，和替換一個字符。題目乍眼一看并不難，但是實際上卻暗藏玄機(jī)，對于兩個字符串的比較，一般都會考慮一下用 HashMap 統(tǒng)計字符出現(xiàn)的頻率，但是在這道題卻不可以這么做，因為字符串的順序很重要。還有一種比較常見的錯誤，就是想當(dāng)然的認(rèn)為對于長度不同的兩個字符串，長度的差值都是要用插入操作，然后再對應(yīng)每位字符，不同的地方用修改操作，但是其實這樣可能會多用操作，因為刪除操作有時同時可以達(dá)到修改的效果。比如題目中的例子1，當(dāng)把 horse 變?yōu)?rorse 之后，之后只要刪除第二個r，跟最后一個e，就可以變?yōu)?ros。實際上只要三步就完成了，因為刪除了某個字母后，原來左右不相連的字母現(xiàn)在就連一起了，有可能剛好組成了需要的字符串。所以在比較的時候，要嘗試三種操作，因為誰也不知道當(dāng)前的操作會對后面產(chǎn)生什么樣的影響。對于當(dāng)前比較的兩個字符 word1[i] 和 word2[j]，若二者相同，一切好說，直接跳到下一個位置。若不相同，有三種處理方法，首先是直接插入一個 word2[j]，那么 word2[j] 位置的字符就跳過了，接著比較 word1[i] 和 word2[j+1] 即可。第二個種方法是刪除，即將 word1[i] 字符直接刪掉，接著比較 word1[i+1] 和 word2[j] 即可。第三種則是將 word1[i] 修改為 word2[j]，接著比較 word1[i+1] 和 word[j+1] 即可。分析到這里，就可以直接寫出遞歸的代碼，但是很可惜會 Time Limited Exceed，所以必須要優(yōu)化時間復(fù)雜度，需要去掉大量的重復(fù)計算，這里使用記憶數(shù)組 memo 來保存計算過的狀態(tài)，從而可以通過 OJ，注意這里的 insertCnt，deleteCnt，replaceCnt 僅僅是表示當(dāng)前對應(yīng)的位置分別采用了插入，刪除，和替換操作，整體返回的最小距離，后面位置的還是會調(diào)用遞歸返回最小的，參見代碼如下：
解法一：
重慶分公司
重慶分公司
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector> memo(m, vector(n));
return helper(word1, 0, word2, 0, memo);
}
int helper(string& word1, int i, string& word2, int j, vector>& 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)驗，對于字符串相關(guān)的題目且求極值的問題，十有八九都是用動態(tài)規(guī)劃 Dynamic Programming 來解，這道題也不例外。其實解法一的遞歸加記憶數(shù)組的方法也可以看作是 DP 的遞歸寫法。這里需要維護(hù)一個二維的數(shù)組 dp，其大小為 mxn，m和n分別為 word1 和 word2 的長度。dp[i][j] 表示從 word1 的前i個字符轉(zhuǎn)換到 word2 的前j個字符所需要的步驟。先給這個二維數(shù)組 dp 的第一行第一列賦值，這個很簡單，因為第一行和第一列對應(yīng)的總有一個字符串是空串，于是轉(zhuǎn)換步驟完全是另一個字符串的長度。跟以往的 DP 題目類似，難點還是在于找出狀態(tài)轉(zhuǎn)移方程，可以舉個例子來看，比如 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
通過觀察可以發(fā)現(xiàn)，當(dāng) word1[i] == word2[j] 時，dp[i][j] = dp[i - 1][j - 1]，其他情況時，dp[i][j] 是其左，左上，上的三個值中的最小值加1，其實這里的左，上，和左上，分別對應(yīng)的增加，刪除，修改操作，具體可以參見解法一種的講解部分，那么可以得到狀態(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> dp(m + 1, vector(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)的知識，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，小編每天都會為大家更新不同的知識點。
