每天一道LeetCode-----使用最少的操作将一个字符串转换成另一个字符串，只有插入，删除，替换三种操作
Edit Distance
原題鏈接Edit Distance
題目要求，輸入兩個字符串word1和word2，計算可以將word1轉換成word2的最小的操作次數，可以執行的操作如下，每個操作算作1次
- 將word1的某個字符刪除
- 在word1當前位置插入一個字符
- 將word1當前位置的字符替換成另一個字符
上面的三個操作每操作一次總操作次數都需要加一，計算最小的操作次數。
這是典型的動態規劃問題。
假設word1的長度為m, word2的長度為n，則可以將word1和word2分別表示成
- word1[0, 1, …, m - 1]
- word2[0, 1, …, n - 1]
那么word1[0, 1, ..., i - 1]就表示word1的前i個字符，word2[0, 1, ..., j - 1]就表示word2的前j個字符
定義dp[i][j]表示將word1[0, 1, ..., i - 1]轉換到word2[0, 1, ..., j - 1]所需要的最小操作次數。
首先明確一點，動態規劃是先求子問題的解，再求實際問題的解，對于本題而言。子問題是對于任意的i和j，計算將word1[0, 1, …, i - 1]轉換成word2[0, 1, …, j - 1]的最小次數，也就是計算所有dp[i][j]的值
當所有子問題的解都計算完畢后，就可以求解最終的實際問題，這里隱含了一個信息，那就是當要求解最終問題時，所有子問題的解是已知的。
假設現在要將word1[0, 1, ..., i - 1]轉換成word2[0, 1, ..., j - 1]，同時假設已經直到了將word1[0, 1, ..., i - 2]轉換成word2[0, 1, ..., j - 2]的最小操作此時，即dp[i - 1][j - 1]。
根據上面的敘述，此時的實際問題是計算dp[i][j]，那么所有子問題的解是已知的，即dp[i - 1][j - 1]，dp[i][j - 1]以及dp[i - 1][j]的值是已經知道的（這里只需要使用這三個子問題的解）
那么
- 如果word1[i - 1] == word2[j - 1]，那么對于將字符word1[i - 1]轉換到word2[j - 1]是不需要任何操作的
- 將word1[0, 1, ..., i - 2]轉換到word2[0, 1, ..., j - 2]，即dp[i][j] = dp[i - 1][j - 1]
- 如果word1[i - 1] != word2[j - 1]，此時有三種方式可以將word1[0, 1, ..., i - 1]轉換到word2[0, 1, ..., j - 1]
- 將word1[i - 1]替換成word2[j - 1]，此時dp[i][j] = 1 + dp[i - 1][j - 1]
- 將word1[i - 1]刪掉，此時dp[i][j] = 1 + dp[i - 1][j]
- 在word1的i - 1位置插入字符word2[ j - 1]，此時dp[i][j] = 1 + dp[i][j - 1]
對于替換操作，因為已經直到將word1[0, 1, ..., i - 2]轉換到word2[0, 1, ..., j - 2]的最小操作次數即dp[i - 1][j - 1]，那么就可以將word1[i - 1]替換成word2[j - 1]。也就是說，可以先將word1[0 , 1, ..., i - 2]轉換到word2[0, 1, ..., j - 2]，然后將word1[i - 1]替換成word2[j - 1]，以達到將word1[0, 1, ..., i - 1]轉換到word2[0, 1, ..., j - 1]的目的
對于刪除操作，因為已經知道將word1[0, 1, ..., i - 2]轉換到word2[0, 1, ..., j - 1]的最小操作數即dp[i - 1][j]，那么就可以將word1[i - 1]刪掉，也就是說，可以先將word1[0, 1, ..., i - 2]轉換到word2[0, 1, ..., j - 1]，然后將word1[i - 1]刪掉，以達到將word1[0, 1, ..., i - 1]轉換到word2[0, 1, ..., j - 1]的目的
對于插入操作，因為已經直到將word1[0, 1, ..., i - 1]轉換到word2[0, 1, ..., j - 2]的最小操作數即dp[i][j - 1]，那么就可以將word1[0, 1, ..., i - 1]的后面添加字符word2[j - 1]，即word1[0, 1, ..., i - 1] + word2[j - 1] == word2[0, 1, ..., j - 1]。也就是說，可以先將word1[0, 1, ..., i - 1]轉換到word2[0, 1, ..., j - 2]，然后在word1[0, 1, ..., i - 1]的后面添加字符word2[j - 1]，以達到將word1[0, 1, ..., i - 1]轉換到word2[0, 1, ..., j - 1]的目的
對于動態規劃而言，有遞歸和迭代兩種方法，遞歸的程序易于理解，但是遞歸的過程造成的棧開銷會影響性能，而迭代恰好相反，不易理解，但是性能高。
遞歸法是從最終問題遞歸到一個最小的子問題上，可以理解成從上向下進行，如果使用遞歸法，那么對于動態規劃數組的定義是需要有所改變的。原因是實際問題要求計算將word1轉換到word2的最小操作，那么隨著遞歸深度的增加最后到達word1[m - 1]和word2[n - 1]，子問題就變成將word1的某個字符轉換成word2的某個字符的最小操作次數。
所以，這里將dp[i][j]的定義改為
- dp[i][j]表示將word1[i, i+1, …, m)轉換到word2[j, j+1, …, n)的最小操作次數。
在實際的操作過程中，仍然使用上述的三種轉換方式
代碼如下
這種方法效率奇低，原因是每次遞歸都需要向三個不同的方向遞歸，即使使用了動態規劃數組減少遞歸次數，但是開銷仍然很大。不過這種方法倒是最容易想到的
迭代法就是模擬遞歸的返回過程，即從最深層的位置向上返回，這就避免后向下遞歸的過程，也沒有所謂的遞歸棧開銷
迭代法的dp定義就和上面相同了，即
- dp[i][j]表示將word1[0, 1, …, i - 1]轉換到word2[0, 1, …, j - 1]的最小操作次數
代碼如下
class Solution { public:int minDistance(string word1, string word2) {int n1 = word1.size();int n2 = word2.size();vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));/* 如果word2為空，那么轉換方式就是將word1每個字符刪掉，次數就是word1的個數 */for(int i = 0; i <= n1; ++i)dp[i][0] = i;/* 如果word1為空，那么轉換方式就是將依次插入word2對應字符，次數就是word2的個數 */for(int j = 0; j <= n2; ++j)dp[0][j] = j;for(int i = 1; i <= n1; ++i){for(int j = 1; j <= n2; ++j){/* 如果對應字符相等，那么只需要將word1[0, 1, ... i - 2]轉換成word2[0, 1, ..., j - 2] */if(word1[i - 1] == word2[j - 1])dp[i][j] = dp[i - 1][j - 1];/* 否則，取三種操作的最小值 */elsedp[i][j] = 1 + std::min(dp[i - 1][j - 1], std::min(dp[i][j - 1], dp[i - 1][j]));}}return dp[n1][n2];} };迭代法的效率比較高（至少從代碼長度上看也是），不過不太容易理解。
將dp設置為(n1 + 1) * (n2 + 1)的原因是根據dp[i][j]的定義，原因dp[i][j]中的i和j分別表示word1和word2的長度，當其中一個是0時，對相當于對應字符串是空字符
- dp[i][0]表示將word1[0, 1, …, i - 1]轉換成空字符，此時操作次數就應該是word1的長度
- dp[0][j]表示將空字符轉換成word2[0, 1, …, j - 1]，此時操作次數就應該是word2的長度
- dp[0][0]表示將空字符轉換成空字符，此時操作次數就應該是0
當然，凡是動態規劃的迭代法都有方法將dp數組降一個維度，這里dp數組是一個二維數組，那么就有辦法用一個一維數組解決問題
對比上面的迭代法，每次循環需要的數值有
- dp[i - 1][j - 1]，表示將word1[0, 1, …, i - 2]轉換成word2[0, 1, …, j - 2]的最小操作次數
- dp[i][j - 1]，表示將word1[0, 1, …, i - 1]轉換成word2[0, 1, …, j - 2]的最小操作次數
- dp[i - 1][j]，表示將word1[0, 1, …, i - 2]轉換成word2[0, 1, …, j - 1]的最小操作次數
那么，可不可以只用一維數組就表示上面三個數值呢。
因為是將word1轉換成word2，那么假設dp數組的定義為vector<int> dp(word1.size() + 1, 0);
定義dp[i]表示將word1[0, 1, ..., i - 1]轉換到word2的最小操作次數，word2的長度是任意的，換句話說，對于任意的j，dp[i]都表示將word1[0, 1, ..., i - 1]轉換到word2[0, 1, ..., j - 1]的最小操作次數。
那么，肯定需要從最小的j開始計算，那么可以先將j放在最外層的for循環中，大體的框架如下
class Solution { public:int minDistance(string word1, string word2) {int n1 = word1.size();int n2 = word2.size();vector<int> dp(n1 + 1, 0);for(int i = 0; i <= n1; ++i)dp[i] = i;for(int j = 1; j <= n2; ++j) //外層{for(int i = 1; i <= n1; ++i) //內層{}}return dp[n1];} };想一下，應該如何表示dp[i - 1][j - 1]，dp[i][j - 1]以及dp[i - 1][j]
假設當j = 1時執行一次內層循環，此時dp1, dp2, …., dp[n1]
當j= 2時再次執行內層循環時，正要計算還沒有計算dp[i]時，dp[i]的值是當j = 1時的值
也就是說此時的dp[i]等價于dp[i][j - 1]
假設當j = 1時執行一次內層循環，在內層循環中計算了dp[1], dp[2], ..., dp[i - 1]
正要計算dp[i]時，dp[i - 1]的值等價于dp[i - 1][j]
假設當j = 1時執行了一次內層循環，此時dp1, dp2, …, dp[n1]
當j = 2時再次執行內層循環，在內層循環中計算了dp[1], dp[2], ..., dp[i]，計算dp[i]時記錄與dp[i][j - 1]等價的dp[i]，也就是還沒有更新dp[i]時的值，記錄在遍歷prev中。
此時prev表示將word1[0, 1, ..., i - 1]轉換成word2[0, 1, ..., j - 2]的值，即dp[i][j - 1]
當計算dp[i + 1]時，prev中的i就變成了i-1，所以表示成dp[i - 1][j - 1]，說明prev正是與dp[i - 1][j - 1]等價的值
（注，如果dp[i + 1 - 1][j - 1]不容易理解，可以將i + 1看成n，此時要計算將word1[0, 1, ..., n - 1]轉換成word2[0, 1, ..., j - 1]的最小操作次數，即dp[n - 1][j - 1]）
以上只是推導了一下二維數組中的dp[i - 1][j - 1]，dp[i][j - 1]和dp[i - 1][j]等價的一維數組對應的值
代碼如下
class Solution { public:int minDistance(string word1, string word2) {int n1 = word1.size();int n2 = word2.size();vector<int> dp(n1 + 1, 0);for(int i = 0; i <= n1; ++i)dp[i] = i;for(int j = 1; j <= n2; ++j){/* dp[0]等價與dp[0][j - 1] */int prev = dp[0];dp[0] = j;for(int i = 1; i <= n1; ++i){/* 此時的dp[i]等價于dp[i][j - 1]，將其賦值給prev* 在下次循環時，prev就代表dp[i - 1][j - 1]* 因為i增加了，此時的i就變為i-1了 */int temp = dp[i];if(word1[i - 1] == word2[j - 1])dp[i] = prev;else/* 此時的dp[i]等價于dp[i][j - 1]，而dp[i - 1]等價于dp[i - 1][j] *//* prev等價于dp[i - 1][j - 1]，因為prev中的i是此時的i - 1 */dp[i] = 1 + std::min(prev, std::min(dp[i], dp[i - 1]));prev = temp;}}return dp[n1];} };上述分別用遞歸，迭代法實現動態規劃，可以發現，遞歸的動態規劃性能不如迭代法。
另外，迭代法可以將動態規劃數組降維，從而進一步減少了空間復雜度
總結
以上是生活随笔為你收集整理的每天一道LeetCode-----使用最少的操作将一个字符串转换成另一个字符串，只有插入，删除，替换三种操作的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 每天一道LeetCode-----化简路
- 下一篇： 每天一道LeetCode-----给定一