C++ 解法, 执行用时: 5ms, 内存消耗: 404KB, 提交时间: 2022-04-29
class Solution {
public:
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* str1 string字符串
* str2 string字符串
* int整型
int editDistance(string str1, string str2) {
int m=str1.size(),n=str2.size();
vector<vector<int>> dp(2,vector<int>(n+1,0));
for(int j=0;j<=n;j++) dp[0][j]=j;
for(int i=1;i<=m;i++){
dp[i%2][0]=i;
for(int j=1;j<=n;j++){
if(str1[i-1]==str2[j-1])
dp[i%2][j]=dp[(i-1)%2][j-1];
else dp[i%2][j]=min({dp[(i-1)%2][j],dp[i%2][j-1],dp[(i-1)%2][j-1]})+1;
}
}
return dp[m%2][n];
}
};
C++ 解法, 执行用时: 5ms, 内存消耗: 464KB, 提交时间: 2022-07-24
class Solution {
public:
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* str1 string字符串
* str2 string字符串
* int整型
int editDistance(string str1, string str2) {
int len1 = str1.size(), len2 = str2.size(), left_up;
vector<int> dp(len2 + 1);
for (int i = 0; i <= len2; ++i) {
dp[i] = i;
}
for (int i = 1; i <= len1; ++i) {
dp[0] = i;
left_up = i - 1;
for (int j = 1; j <= len2; ++j) {
int up = dp[j];
if (str1[i - 1] == str2[j - 1]) {
dp[j] = left_up;
}
else {
dp[j] = min({dp[j], dp[j - 1], left_up}) + 1;
}
left_up = up;
}
}
return dp[len2];
}
};
C++ 解法, 执行用时: 6ms, 内存消耗: 396KB, 提交时间: 2022-07-13
class Solution {
public:
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* str1 string字符串
* str2 string字符串
* int整型
int editDistance(string str1, string str2) {
if(str1.empty())
return str2.size();
if(str2.empty())
return str1.size();
vector<int> preArr(str2.size()+1, 0);
for(int j=1;j<=str2.size();++j)
preArr[j] = j;
for(int i=1;i<=str1.size();++i){
vector<int> tmp(str2.size()+1, 0);
tmp[0] = i;
for(int j=1;j<=str2.size();++j){
if(str1[i-1] == str2[j-1])
tmp[j] = preArr[j-1];
else{
tmp[j] = min(1+tmp[j-1], 1+preArr[j]);
tmp[j] = min(tmp[j], 1+preArr[j-1]);
}
}
preArr = move(tmp);
}
return preArr.back();
}
};
C++ 解法, 执行用时: 6ms, 内存消耗: 396KB, 提交时间: 2022-05-11
class Solution {
public:
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* str1 string字符串
* str2 string字符串
* int整型
int editDistance(string str1, string str2) {
int n1 = str1.size();
int n2 = str2.size();
vector<int> dp(n2 + 1, 0);
for(int i = 1; i <= n2; ++ i) dp[i] = i;
for(int i = 1; i <= n1; ++ i)
{
int pre = dp[0];
dp[0] = i;
int temp;
for(int j = 1; j <= n2; ++ j)
{
temp = dp[j];
if(str1[i - 1] == str2[j - 1])
{
dp[j] = pre;
}
else
{
dp[j] = min(dp[j], min(pre, dp[j - 1])) + 1;
}
pre = temp;
}
}
return dp[n2];
}
};
C++ 解法, 执行用时: 6ms, 内存消耗: 416KB, 提交时间: 2022-07-09
class Solution {
public:
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* str1 string字符串
* str2 string字符串
* int整型
int editDistance(string str1, string str2) {
int n1 = str1.length();
int n2 = str2.length();
if(n1 == 0) return n2;
if(n2 == 0) return n1;
int dp[2][n2+1];
dp[0][0] = 0;
for(int j = 1; j <= n2; ++j){
dp[0][j] = j;
}
for(int i = 1; i <= n1; ++i){
dp[i % 2][0] = i;
for(int j = 1; j <= n2; ++j){
if(str1[i-1] == str2[j-1]){
dp[i%2][j] = dp[(i-1)%2][j-1];
}else{
dp[i%2][j] = min(dp[(i-1)%2][j-1], min(dp[(i-1)%2][j], dp[i%2][j-1])) + 1;
}
}
}
return dp[n1%2][n2];
}
};