LeetCode 583 两个字符串的删除操作
题目链接:https://leetcode.cn/problems/delete-operation-for-two-strings/
思路:
方法一:两个子串同时删除元素
-
dp数组的含义
d p [ i ] [ j ] dp[i][j] dp[i][j]代表以i-1为结尾的字符串word1,和以j-1位结尾的字符串word2,想要达到相等,所需要删除元素的最少次数 -
递推公式
本题有两种情况:
word1[i - 1] == word2[j - 1]
显然此时递推公式为:
d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 dp[i][j] = dp[i-1][j-1]+1 dp[i][j]=dp[i−1][j−1]+1
word1[i - 1] != word2[j - 1]
此时有三种情况:
1. 删除word1里的第i-1个元素
d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + 1 dp[i][j] = dp[i-1][j]+1 dp[i][j]=dp[i−1][j]+1
2. 删除word2里的第i-1个元素
d p [ i ] [ j ] = d p [ i ] [ j − 1 ] + 1 dp[i][j] = dp[i][j-1]+1 dp[i][j]=dp[i][j−1]+1
3. 同时删除word1和word2里的第i-1个元素
d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 dp[i][j] = dp[i-1][j-1]+1 dp[i][j]=dp[i−1][j−1]+1
因为要求的是最小值,所以总的递推公式为:
d p [ i ] [ j ] = m i n ( d p [ i − 1 ] [ j ] + 1 , d p [ i ] [ j − 1 ] + 1 , d p [ i − 1 ] [ j − 1 ] + 1 ) dp[i][j] = min({dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1}) dp[i][j]=min(dp[i−1][j]+1,dp[i][j−1]+1,dp[i−1][j−1]+1) -
初始化
d p [ i ] [ 0 ] dp[i][0] dp[i][0]代表word1要和空字符相等需要多少次删除操作,显然为i;同理, d p [ 0 ] [ j ] dp[0][j] dp[0][j]代表word2要和空字符 相等需要多少次删除操作,显然为j,所以初始化操作如下:for(int i = 0; i <= word1.size(); i++) dp[i][0] = i; for(int j = 0; j <= word2.size(); j++) dp[0][j] = j;
-
遍历顺序
显然遍历是从上到下,从左到右
代码:
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][j - 1] + 1, dp[i - 1][j] + 1, dp[i - 1][j - 1] + 2});
}
}
return dp[word1.size()][word2.size()];
}
};
方法二:求出最长公共子序后,两个字符串分别减去最长公共子序的长度
- dp数组的含义
d p [ i ] [ j ] dp[i][j] dp[i][j]代表以i-1为结尾的字符串word1,和以j-1位结尾的字符串word2的最长公共子序的长度 - 递推公式
本题有两种情况:
word1[i - 1] == word2[j - 1]
显然此时递推公式为:
d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 dp[i][j] = dp[i-1][j-1]+1 dp[i][j]=dp[i−1][j−1]+1
word[i - 1] != word[j - 1]
例子:text1:abc text2:ace
有两种情况:
因为最后c和e不相同,所以可以是abc和ac相比,得出公共子序列的长度,也可以是ab和ace相比
所以此时递推公式是:
d p [ i ] [ j ] = m a x ( d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j ] ) dp[i][j] = max(dp[i][j-1],dp[i-1][j]) dp[i][j]=max(dp[i][j−1],dp[i−1][j]) - 初始化
dp[i][0]和dp[0][j]显然都是没有意义的,即二维数组的第一行和第一列,将其全部初始化为0即可。其余数值因为会在递推公式中被覆盖,所以也都初始化为0,这样可以使得代码相对简洁。 - 遍历顺序
显然遍历是从上到下,从左到右
代码
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]);
}
}
int result = word1.size() + word2.size() - 2 * dp[word1.size()][word2.size()];
return result;
}
};
总结
想到了第二种方法,第一种方法不相等时候的情况没有考虑清楚。
LeetCode 72 编辑距离
题目链接:https://leetcode.cn/problems/edit-distance/
思路:
-
dp数组的含义
dp[i][j]dp[i][j] 表示以下标i-1为结尾的字符串word1变为以下标j-1为结尾的字符串word2的最小的操作数为。 -
递推公式
本题有两种情况:
word1[i - 1] == word2[j - 1]
此时说明需要继续向后修改即可。
所以此时递推公式为:
d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] dp[i][j] = dp[i-1][j-1] dp[i][j]=dp[i−1][j−1]word1[i - 1] != word2[j - 1]
有三种操作方法:
1. 删除word1的第i-1个元素
此时递推公式为:
d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + 1 dp[i][j] = dp[i-1][j]+1 dp[i][j]=dp[i−1][j]+1
2. 替换word1的第i-1个元素
那么就要在 d p [ i − 1 ] [ j − 1 ] dp[i-1][j-1] dp[i−1][j−1](以i-2为结尾的word1子串和以j-2结尾的word2子串)的基础上对word1的第i-1个元素进行操作,所以此时递推公式为:
d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 dp[i][j] = dp[i-1][j-1]+1 dp[i][j]=dp[i−1][j−1]+1
3. 在word1的第i-2个元素后添加一个元素
在word1添加一个元素,相当于word2删除一个元素,例如 word1 = “a” ,word2 = “ad”,word2删除元素’d’ 和 word1添加一个元素’d’,变成word1=“ad”, word2=“a”, 最终的操作数是一样!
所以此时递推公式为:
d p [ i ] [ j ] = d p [ i ] [ j − 1 ] + 1 dp[i][j] = dp[i][j-1]+1 dp[i][j]=dp[i][j−1]+1
dp数组如下图所示意a a d +-----+-----+ +-----+-----+-----+ | 0 | 1 | | 0 | 1 | 2 | +-----+-----+ ===> +-----+-----+-----+ a | 1 | 0 | a | 1 | 0 | 1 | +-----+-----+ +-----+-----+-----+ d | 2 | 1 | +-----+-----+
所以总体的递推公式为:
d p [ i ] [ j ] = m i n ( d p [ i − 1 ] [ j ] + 1 , d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 , d p [ i ] [ j ] = d p [ i ] [ j − 1 ] + 1 ) dp[i][j] = min({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]=min(dp[i−1][j]+1,dp[i][j]=dp[i−1][j−1]+1,dp[i][j]=dp[i][j−1]+1) -
初始化
d p [ i ] [ 0 ] dp[i][0] dp[i][0]代表word1要和空字符相等需要多少次删除操作,显然为i;同理, d p [ 0 ] [ j ] dp[0][j] dp[0][j]代表word2要和空字符 相等需要多少次删除操作,显然为j,所以初始化操作如下:for(int i = 0; i <= word1.size(); i++) dp[i][0] = i; for(int j = 0; j <= word2.size(); j++) dp[0][j] = j;
-
遍历顺序
显然遍历是从上到下,从左到右
代码:
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][j - 1] + 1, dp[i - 1][j - 1] + 1});
}
}
return dp[word1.size()][word2.size()];
}
};
总结
重点要理解word1添加元素相当于word2删除元素
今日总结:
学习了编辑距离问题。