Given two strings word1
and word2
, return the minimum
number of operations required to convert word1
to word2
.
You have the following three operations permitted on a word:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
0 <= word1.length, word2.length <= 500
word1 and word2 consist of lowercase English letters.
AC:
/*
* @lc app=leetcode.cn id=72 lang=cpp
*
* [72] 编辑距离
*/
// @lc code=start
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], dp[i - 1][j - 1]}) + 1;
}
}
}
return dp[word1.size()][word2.size()];
}
};
// @lc code=end
if (word1[i - 1] != word2[j - 1])
,此时就需要编辑了,如何编辑呢?
操作一:word1
删除一个元素,那么就是以下标i - 2
为结尾的word1
与 j-1
为结尾的word2
的最近编辑距离
再加上一个操作。
即 dp[i][j] = dp[i - 1][j] + 1;
操作二:word2
删除一个元素,那么就是以下标i - 1
为结尾的word1
与 j-2
为结尾的word2
的最近编辑距离
再加上一个操作。
即 dp[i][j] = dp[i][j - 1] + 1;
word2
添加一个元素,相当于word1
删除一个元素,例如 word1 = "ad" ,word2 = "a"
,word1
删除元素'd'
和 word2
添加一个元素'd'
,变成word1="a"
, word2="ad"
, 最终的操作数是一样!
除此之外,需要强调下·max·,·min·函数的使用方法:
在C++中,min
和max
函数可以用于返回两个数中的最小值和最大值,一般情况下,它们的用法如下:
int a = 10, b = 20;
int minVal = min(a, b);
int maxVal = max(a, b);
然而,在某些特定的情况下,如果不使用{}
,可能会导致错误。例如:
int a = 10, b = 20;
int c = max(a, b + 1) * 2;
上述代码中,max
函数的参数不止一个,因此需要使用()
来表示函数参数列表,但是由于乘法运算符*
的优先级更高,如果不使用{}
,可能会得到错误的结果。具体来说,上述代码实际上相当于:
int c = max(a, (b + 1) * 2); // c = 40,错误的结果
而如果使用{}
将max
函数的参数列表括起来,则可以得到正确的结果:
int c = max(a, {b + 1}) * 2; // c = 22,正确的结果
因此,在使用min
和max
函数时,如果参数列表中包含有其他运算符或表达式,最好使用{}
来明确参数列表的边界。
在max
函数中,使用大括号括起来的是可迭代对象,如列表、元组、集合等。如果我们要对一个可迭代对象中的元素进行比较,那么就可以使用max({})
这种形式。
lst = [5, 10, 2, 8]
max_value = max(lst)
print(max_value)
输出结果为:
10
lst = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
如果要从这个列表中找到元素之和最大的子列表,我们可以使用max
函数来实现:
max_value = max(lst, key=sum)
print(max_value)
输出结果为:
[7, 8, 9]
这里的key=sum
表示按照子列表元素之和的大小进行比较,返回元素之和最大的子列表。注意,这里传入的是列表lst
,而不是{lst}
,因为lst
本身就是一个可迭代对象。在max
函数中,使用大括号括起来的是可迭代对象,如列表、元组、集合等。如果我们要对一个可迭代对象中的元素进行比较,那么就可以使用max({})
这种形式。
例如,如果我们要找到下列列表中的最大值:
lst = [5, 10, 2, 8]
我们可以使用max
函数来实现:
max_value = max(lst)
print(max_value)
输出结果为:
10
lst = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
如果要从这个列表中找到元素之和最大的子列表,我们可以使用max
函数来实现:
max_value = max(lst, key=sum)
print(max_value)
输出结果为:
[7, 8, 9]
这里的key=sum
表示按照子列表元素之和的大小进行比较,返回元素之和最大的子列表。注意,这里传入的是列表lst
,而不是{lst}
,因为lst
本身就是一个可迭代对象。
原文地址:https://blog.csdn.net/qq_54053990/article/details/134693896
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_12599.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!