leetcode 583. 兩個字符串的刪除操作

題目鏈接：兩個字符串的刪除操作
兩個字符串可以相互刪除

版本一：

1. 確定dp數(shù)組及下標(biāo)的含義
   dp[i][j]：以i-1為結(jié)尾的字符串word1，和以j-1為結(jié)尾的字符串word2，想要達(dá)到相等，所需要刪除元素的最少次數(shù)
2. 確定遞推公式
   （1）當(dāng)word1[i - 1] 與 word2[j - 1]相同：

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

（2）當(dāng)word1[i - 1] 與 word2[j - 1]不相同：
情況一：刪word1[i - 1]，最少操作次數(shù)為dp[i - 1][j] + 1
情況二：刪word2[j - 1]，最少操作次數(shù)為dp[i][j - 1] + 1
情況三：同時刪word1[i - 1]和word2[j - 1]，操作的最少次數(shù)為dp[i - 1][j - 1] + 2
則dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1})
由于同時刪word1[i - 1]和word2[j - 1]，相當(dāng)于dp[i][j-1] 基礎(chǔ)上不考慮word2[j - 1]，刪除word1[i - 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)

3. dp數(shù)組初始化

vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;

4. 確定遍歷順序
   從左到右，從上到下

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
        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()];
    }
};

版本二：

求出兩個字符串的最長公共子序列長度，除了最長公共子序列之外的字符都是必須刪除的，用兩個字符串的總長度減去兩個最長公共子序列的長度就是刪除的最少步數(shù)。

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
        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] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return word1.size() + word2.size() - 2*dp[word1.size()][word2.size()];
    }
};

leetcode 72. 編輯距離

題目鏈接：編輯距離

1. 確定dp數(shù)組及下標(biāo)的含義
   dp[i][j]：以i-1為結(jié)尾的字符串word1，和以j-1為結(jié)尾的字符串word2，最近的編輯距離
2. 確定遞推函數(shù)
   （1）如果word1[i - 1] == word2[j - 1]：不用編輯，dp[i][j] = dp[i - 1][j - 1]
   （2）如果word1[i - 1] != word2[j - 1]：（一個字符串添加一個元素，相當(dāng)于另一個字符串刪除一個元素，所以刪除和添加可以轉(zhuǎn)換）三種情況取最小值
   操作一：word1刪除一個元素，dp[i][j] = dp[i - 1][j] + 1
   操作二：word2刪除一個元素，dp[i][j] = dp[i ][j -1] + 1
   操作三：替換元素，word1替換word1[i - 1]，使其與word2[j - 1]相同，此時不用增刪元素，dp[i][j] = dp[i - 1][j - 1] + 1
   所以遞推公式：

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 - 1][j], dp[i][j - 1]}) + 1;
}

3. dp數(shù)組初始化

for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;

4. 確定遍歷順序
   從前到后，從上到下

class Solution {
public:
    int minDistance(string word1, string word2) {
        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 - 1][j], dp[i][j - 1]}) + 1;
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

時間復(fù)雜度: O(n * m)
空間復(fù)雜度: O(n * m)文章來源地址http://www.zghlxwxcb.cn/news/detail-783289.html

到了這里，關(guān)于代碼隨想錄第五十六天——兩個字符串的刪除操作，編輯距離的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！