_48LeetCode代碼随想錄算法訓練營第四十八天-動态規劃 | 583.兩個字元串的删除操作、72.編輯距離、編輯距離總結篇

題目清單

583.兩個字元串的删除操作
72.編輯距離
編輯距離總結篇

583.兩個字元串的删除操作

代碼随想錄位址：https://programmercarl.com/0583.%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C.html

題目

給定兩個單詞

word1

和

word2

，傳回使得

word1

和

word2

相同所需的最小步數。

每步可以删除任意一個字元串中的一個字元。

示例 1：

輸入: word1 = "sea", word2 = "eat"
輸出: 2
解釋: 第一步将 "sea" 變為 "ea" ，第二步将 "eat "變為 "ea"

示例 2:

輸入：word1 = "leetcode", word2 = "etco"
輸出：4

提示：

1 <= word1.length, word2.length <= 500
word1 和 word2 隻包含小寫英文字母

思路

确定dp數組（dp table）以及下标的含義

dp[i] [j]：以i-1為結尾的字元串word1，和以j-1位結尾的字元串word2，想要達到相等，所需要删除元素的最少次數。

這裡dp數組的定義有點點繞，大家要撸清思路。

确定遞推公式

當word1[i - 1] 與 word2[j - 1]相同的時候
當word1[i - 1] 與 word2[j - 1]不相同的時候

當word1[i - 1] 與 word2[j - 1]相同的時候，dp[i] [j] = dp[i - 1] [j - 1];(就是不删)

當word1[i - 1] 與 word2[j - 1]不相同的時候，有三種情況：

情況一：删word1[i - 1]，最少操作次數為dp[i - 1] [j] + 1

情況二：删word2[j - 1]，最少操作次數為dp[i] [j - 1] + 1

情況三：同時删word1[i - 1]和word2[j - 1]，操作的最少次數為dp[i - 1] [j - 1] + 2

那最後當然是取最小值，是以當word1[i - 1] 與 word2[j - 1]不相同的時候，遞推公式：dp[i] [j] = min({dp[i - 1] [j - 1] + 2, dp[i - 1] [j] + 1, dp[i] [j - 1] + 1});

因為 dp[i] [j - 1] + 1 = dp[i - 1] [j - 1] + 2，是以遞推公式可簡化為：dp[i] [j] = min(dp[i - 1] [j] + 1, dp[i] [j - 1] + 1);

dp數組如何初始化

從遞推公式中，可以看出來，dp[i] [0] 和 dp[0] [j]是一定要初始化的。

dp[i] [0]：word2為空字元串，以i-1為結尾的字元串word1要删除多少個元素，才能和word2相同呢，很明顯dp[i] [0] = i。

dp[0] [j]的話同理

确定周遊順序

是以周遊的時候一定是從上到下，從左到右。

動态推導dp數組

草稿紙。

代碼

時間複雜度：O(m * n) ，m表示word1的元素個數， n表示word2的元素個數。
空間複雜度：O(m * n)

/*
 * @lc app=leetcode.cn id=583 lang=cpp
 *
 * [583] 兩個字元串的删除操作
 */

// @lc code=start
class Solution {
public:
    int minDistance(string word1, string word2) {
        //定義及初始化dp數組
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
        for(int i = 0; i <= word1.size(); i++)
            dp[i][0] = i;
        for(int j = 0; j <= word2.size(); j++)
            dp[0][j] = j;
        //周遊
        for(int i = 1; i <= word1.size(); i++)
            for(int j = 1; j <= word2.size(); 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, dp[i][j - 1] + 1);
            }
        return dp[word1.size()][word2.size()];
    }
};
// @lc code=end

時間複雜度：O(m * n) ，m表示word1的元素個數， n表示word2的元素個數。
空間複雜度：O(n)

/*
 * @lc app=leetcode.cn id=583 lang=cpp
 *
 * [583] 兩個字元串的删除操作
 */

// @lc code=start
class Solution {
public:
    int minDistance(string word1, string word2) {
        //定義及初始化dp數組
        vector<vector<int>> dp(2, vector<int>(word2.size() + 1, 0));
        for(int j = 0; j <= word2.size(); j++)
            dp[0][j] = j;
        //周遊
        for(int i = 1; i <= word1.size(); i++)
        {
            dp[i % 2][0] = i;//每次都要重新初始化dp[i % 2][0],因為後面的遞推公式會用到，相當于dp數組列的初始化
            for(int j = 1; j <= word2.size(); j++)
            {
                
                if(word1[i - 1] == word2[j - 1])
                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1];
                else
                    dp[i % 2][j] = min(dp[(i - 1) % 2][j] + 1, dp[i % 2][j - 1] + 1);
            }
        }            
        return dp[word1.size() % 2][word2.size()];
    }
};
// @lc code=end

72.編輯距離

代碼随想錄位址：https://programmercarl.com/0072.%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.html

題目

給你兩個單詞

word1

和

word2

，請傳回将 word1 轉換成 word2 所使用的最少操作數。

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

插入一個字元
删除一個字元
替換一個字元

示例 1：

輸入：word1 = "horse", word2 = "ros"
輸出：3
解釋：
horse -> rorse (将 'h' 替換為 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

輸入：word1 = "intention", word2 = "execution"
輸出：5
解釋：
intention -> inention (删除 't')
inention -> enention (将 'i' 替換為 'e')
enention -> exention (将 'n' 替換為 'x')
exention -> exection (将 'n' 替換為 'c')
exection -> execution (插入 'u')

提示：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小寫英文字母組成

思路

确定dp數組（dp table）以及下标的含義

dp[i] [j] 表示以下标i-1為結尾的字元串word1，和以下标j-1為結尾的字元串word2，最近編輯距離為dp[i] [j]。

确定遞推公式

在确定遞推公式的時候，首先要考慮清楚編輯的幾種操作，整理如下：

if (word1[i - 1] == word2[j - 1])
    不操作
if (word1[i - 1] != word2[j - 1])
    增
    删
    換

if (word1[i - 1] == word2[j - 1])

 那麼不用編輯，

dp[i] [j]

就應該是

dp[i - 1] [j - 1]

，即

dp[i] [j] = dp[i - 1] [j - 1];

if (word1[i - 1] != word2[j - 1])

，此時就需要編輯了，如何編輯呢？

操作一删：如果到dp[i - 1] [j]需要k步，那麼到dp[i] [j] 需要多少步呢？此時就需要删除word1[i - 1]才可達到，于是 dp[i][j] = dp[i - 1][j] + 1 = k + 1;
操作二增：如果到dp[i] [j - 1]需要k步，那麼達到dp[i] [j]需要多少步呢？此時就需要删除word2[j - 1]才可達到(删除word2[j- 1]就相當于增word1[i - 1])；是以， dp[i][j] = dp[i][j - 1] + 1 = k + 1;
操作三換：替換元素， 替換 word1[i - 1] ，使其與
word2[j - 1]相同，此時不用增删加元素。

其實就是dp[i - 1] [j - 1]加一步轉化而來。

dp數組如何初始化

dp[i] [0] ：以下标i-1為結尾的字元串word1，和空字元串word2，最近編輯距離為dp[i] [0]。

那麼dp[i] [0]就應該是i，對word1裡的元素全部做删除操作，即：dp[i] [0] = i;

同理dp[0] [j] = j;(此時就是填的操作了)

确定周遊順序

從如下四個遞推公式：

dp[i][j] = dp[i - 1][j - 1]
dp[i][j] = dp[i - 1][j - 1] + 1
dp[i][j] = dp[i][j - 1] + 1
dp[i][j] = dp[i - 1][j] + 1

可以看出dp[i][j]是依賴左方，上方和左上方元素的，如圖：

_48LeetCode代碼随想錄算法訓練營第四十八天-動态規劃 | 583.兩個字元串的删除操作、72.編輯距離、編輯距離總結篇_48LeetCode代碼随想錄算法訓練營第四十八天-動态規劃 | 583.兩個字元串的删除操作、72.編輯距離、編輯距離總結篇583.兩個字元串的删除操作72.編輯距離編輯距離總結篇

是以在dp矩陣中一定是從左到右從上到下去周遊。

舉例推導dp數組

以示例1為例，輸入：

word1 = "horse", word2 = "ros"

為例，dp矩陣狀态圖如下：

代碼

時間複雜度：O(m * n) ，m表示word1的元素個數， n表示word2的元素個數。
空間複雜度：O(m * n)

/*
 * @lc app=leetcode.cn id=72 lang=cpp
 *
 * [72] 編輯距離
 */

// @lc code=start
class Solution {
public:
    int minDistance(string word1, string word2) {
        //定義dp數組
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
        //初始化dp數組
        for(int i = 0;  i <= word1.size(); i++)
            dp[i][0] = i;
        for(int j = 0; j <= word2.size(); j++)
            dp[0][j] = j;
        
        //周遊
        for(int i = 1; i <= word1.size(); i++)
            for(int j = 1; j <= word2.size(); 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, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1});
            }
        return dp[word1.size()][word2.size()];
    }
};
// @lc code=end

優化空間複雜度：

時間複雜度：O(m * n) ，m表示word1的元素個數， n表示word2的元素個數。
空間複雜度：O(n)

/*
 * @lc app=leetcode.cn id=72 lang=cpp
 *
 * [72] 編輯距離
 */

// @lc code=start
class Solution {
public:
    int minDistance(string word1, string word2) {
        //定義dp數組
        vector<vector<int>> dp(2, vector<int>(word2.size() + 1, 0));
        //初始化dp數組
        for(int j = 0; j <= word2.size(); j++)
            dp[0][j] = j;
        
        //周遊
        for(int i = 1; i <= word1.size(); i++)
        {
            dp[i % 2][0] = i;//每次都要重新初始化首列的元素，和初始化dp一個道理
            for(int j = 1; j <= word2.size(); j++)
            {
                
                if(word1[i - 1] == word2[j - 1])
                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1];
                else
                    dp[i % 2][j] = min({dp[(i - 1) % 2][j] + 1, dp[i % 2][j - 1] + 1, dp[(i - 1) % 2][j - 1] + 1});
            }
        }            
        return dp[word1.size() % 2][word2.size()];
    }
};
// @lc code=end

編輯距離總結篇

代碼随想錄位址：https://programmercarl.com/%E4%B8%BA%E4%BA%86%E7%BB%9D%E6%9D%80%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB%EF%BC%8C%E5%8D%A1%E5%B0%94%E5%81%9A%E4%BA%86%E4%B8%89%E6%AD%A5%E9%93%BA%E5%9E%AB.html

_48LeetCode代碼随想錄算法訓練營第四十八天-動态規劃 | 583.兩個字元串的删除操作、72.編輯距離、編輯距離總結篇

583.兩個字元串的删除操作

題目

思路

代碼

72.編輯距離

題目

思路

代碼

編輯距離總結篇

繼續閱讀

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

HDU 1160 FatMouse's Speed （記錄路徑的最長上升子序列）

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

27. Remove Element(清單)題目代碼

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

線性表之順序表的實作

LeetCode OJ Binary Tree Right Side View

leetcode809

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

hdu7108哈希