代码随想录训练营第56天|LeetCode 583. 两个字符串的删除操作、72. 编辑距离

参考

代码随想录

题目一：LeetCode 583. 两个字符串的删除操作

1. 确定dp数组下标及其含义
   为了方便dp数组的初始化，在整个分析问题的过程中在word1和word2的最前面添加空字符，注意，不是真正的添加，只是这么认为。
   dp[i][j]：word1中的0～i字符和word2中的0～j字符相等的最少删除次数。

2. 确定递推公式

• 如果word1[i] == word2[j]，则dp[i][j] = dp[i-1][j-1]，因为word1[i]和word2[j]已经相等，所以这两个字符不需要删除，只需要对前0～i-1个字符和0～j-1个字符进行匹配就可以了。
• 如果word1[i] != word2[j]，则dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + 1，因为此时有两种方式，一种是删除word[i],即dp[i][j] = dp[i-1][j] + 1，另一种是删除word2[j]，即dp[i][j] = do[i][j-1] + 1.

3. 初始化dp数组
   在之前已经说过，在求解过程中在word1和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;
1
2
3

如果没有空字符，则初始化如下图所示：

代码实现如下：

vector<vector<int>> dp(word1.size(),vector<int>(word2.size()));
bool flag;
dp[0][0] = word1[0] == word2[0] ? 0 : 2;
flag = word1[0] == word2[0] ? true : false;
for(int i = 1; i < word1.size(); i++){
    if(word1[i] == word2[0])    flag = true;
    if(flag == true)    dp[i][0] = i;
    else    dp[i][0] = i + 2;
}
flag = word1[0] == word2[0] ? true : false;
for(int j = 1; j < word2.size(); j++){
    if(word1[0] == word2[j])    flag = true;
    if(flag == true)    dp[0][j] = j;
    else    dp[0][j] = j + 2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

可以看出，没有空字符时初始化过程要复杂得多。当然，添加空字符的好处也仅仅是在初始化上，在遍历过程中两种都是一样的。

4. 确定遍历顺序
   从左到右，从上到下遍历。

5. 举例推导dp数组
   完整的代码实现如下：

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],dp[i][j-1]) + 1;
            }
        }
        return dp.back().back();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

题目二：LeetCode 72. 编辑距离

1. 确定dp数组下标及其含义
   和上一个题一样，两个字符串添加空字符，方便初始化。
   dp[i][j]：子串1（word1中的0～i字符构成的字符串，包含i）转换成子串2（word2中的0～j字符构成的字符串，包含j）需要的最少操作数为dp[i][j]。

2. 确定递推公式
   如果word1[i] == word2[j]，则dp[i][j] = dp[i-1][j-1]，这很好理解，当前的两个字符已经相等，因此变换次数和之前的一致。
   如果word1[i] != word2[j]，则可以有增加、删除和替换三种操作，如下图所示：
   
   上图中的阴影区域处，word1[i] = ‘r’ != word2[j] = ‘s’，此时对应的子串1为"hor"，子串2为"ros"，有三种方式将子串1变换为子串2。图中标注的1表示的是增加操作，从"hor"变为"ro"已经知道最少需要dp[i][j-1]次，只要在"ro"后面增加字符s，就可以得到"ros"，因此增加操作需要dp[i][j-1]操作；图中标注的2是替换操作，将"ho"变换为"ro"需要dp[i-1][j-1]次，只需要将"hor"末尾的’r’替换为’s’就可以得到’ros’，因此替换操作需要dp[i-1][j-1] + 1次操作；图中标注的3是删除操作，"ho"到"ros"需要dp[i-1][j]次操作，现在从"hor"到"ros"只需要删除末尾的’r’即可，因此删除操作需要dp[i-1][j] + 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;
1
2
3
4

3. 初始化dp数组
   根据递推公式，需要初始化dp数组的第0行和第0列，代码如下：

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;
1
2
3

4. 确定遍历顺序
   根据递推公式，从左到右，从上到下遍历即可。

5. 举例推导dp数组
   
   完整的代码实现如下：

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-1][j],dp[i][j-1]}) + 1;
            }
        } 
        return dp.back().back();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17