題目分析

題目鏈接：https://leetcode.com/problems...
對于長度為x的字符串s1和長度為y的字符串s2，從s1改變成s2最少要經過多少次“增加”、“刪除”或“替換”？

為了使用動態規劃算法，要先將父問題分解成子問題（父問題和子問題是同一種問題，只不過分解得到的子問題規模更小）。
那么現在就需要我們找出父問題和子問題之間的轉移關系。推導父子問題之間的轉移關系有2中思路：

• 要解決父問題，需要先解決哪些子問題

  • 要求解兩個字符串之間的最小編輯距離，需要用到哪些更小的字符串之間的編輯距離？

• 假設已經知道一些子問題的答案，能計算出哪些同一類型、規模更大的父問題

  • 如果已經知道某一對字符串之間的編輯距離（已經知道一些子問題），能推導出哪些字符串之間的最小編輯距離（這些子問題能求解出哪些父問題）

在這個問題中，使用第一種思路更簡單。
假設要求s3與s4兩個字符串之間的最小編輯距離，有下面兩種情況：

• 如果s3與s4的結尾字符相同，那么答案等于s3與s4都去掉結尾字符以后的最小編輯距離（子問題）

• 如果s3與s4的結尾字符不同，那么先不管前面的那些字符，如何編輯s3使得兩個字符串的結尾字符相同呢？測試幾個例子能知道，結尾字符最終相同只能有以下3種原因：

  • 向s3后面拼接s4的結尾字符。此時，原始s3與s4的最小編輯距離=1+拼接以后的最小編輯距離
  • 刪除s3的結尾字符（可能刪除以后結尾字符還是不同，不過沒關系，這是子問題要處理的事情）。此時，原始s3與s4的最小編輯距離=1+刪除以后的最小編輯距離
  • 將s3的結尾字符替換成了s4的結尾字符。此時，原始s3與s4的最小編輯距離=1+替換以后的最小編輯距離

除了以上三種手段以外，不管你如何對s3的前面字符如何增加、刪除、替換，都不能讓結尾字符相同。

現在將上面結論換成代碼表述。假設ed[i][j]表示 word1[0]~word1[i-1]與word2[0]~word2[j-1]之間的最小編輯距離

if (word1[i - 1] == word2[j - 1]) ed[i][j] = ed[i - 1][j - 1]; else ed[i][j] = min(min(ed[i][j - 1] + 1, ed[i - 1][j] + 1), ed[i - 1][j - 1] + 1); // 將3種方法都嘗試，取最小的結果

現在有了轉移關系，我們只要先計算子問題的結果（較短子串之間的編輯距離）并存儲起來，然后用它計算出父問題的結果（較長子串之間的編輯距離），最后就能算出兩個完整字符串之間的編輯距離。

代碼實現

class Solution {public:int minDistance(string word1, string word2){const int size1 = word1.size(),size2 = word2.size();if (size1 == 0)return size2;if (size2 == 0)return size1;// ed[i][j]表示 word1[0]~word1[i-1]與word2[0]~word2[j-1]之間的最小編輯距離vector<vector<int>> ed(size1 + 1, vector<int>(size2 + 1, 0));// 初始化任意字符與空字符之間的編輯距離for (int i = 0; i <= size1; i++){ed[i][0] = i;}for (int i = 0; i <= size2; i++){ed[0][i] = i;}for (int i = 1; i <= size1; i++){for (int j = 1; j <= size2; j++){if (word1[i - 1] == word2[j - 1])ed[i][j] = ed[i - 1][j - 1];else// 將3種編輯結尾的方法都嘗試，取最小的結果ed[i][j] = min(min(ed[i][j - 1] + 1, ed[i - 1][j] + 1), ed[i - 1][j - 1] + 1);}}return ed[size1][size2];} };

使用了2層嵌套循環，對每一種word1和word2的前綴的組合都求出了編輯距離，因此時間復雜度是O(n^2)。

在這里，數組ed具有更一般的含義：它是動態規劃算法的記憶存儲，存儲了已經計算出的子問題的答案。更嚴格地說，其實只需要存儲將來可能被父問題用到的計算結果。

總結

以上是生活随笔為你收集整理的算法题解：最小编辑距离（动态规划算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。