列表

详情


BM75. 编辑距离(一)

描述

给定两个字符串 str1 和 str2 ,请你算出将 str1 转为 str2 的最少操作数。
你可以对字符串进行3种操作:
1.插入一个字符
2.删除一个字符
3.修改一个字符。

字符串长度满足 ,保证字符串中只出现小写英文字母。

示例1

输入:

"nowcoder","new"

输出:

6

说明:

"nowcoder"=>"newcoder"(将'o'替换为'e'),修改操作1次 "nowcoder"=>"new"(删除"coder"),删除操作5次

示例2

输入:

"intention","execution"

输出:

5

说明:

一种方案为: 因为2个长度都是9,后面的4个后缀的长度都为"tion",于是从"inten"到"execu"逐个修改即可

示例3

输入:

"now","nowcoder"

输出:

5

原站题解

import java.util.*;
public class Solution {
/**
*
*
*
* @param str1 string
* @param str2 string
* @return int
*/
public int editDistance (String str1, String str2) {
// write code here
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

C++ 解法, 执行用时: 5ms, 内存消耗: 404KB, 提交时间: 2022-04-29

class Solution {
public:
/**
*
*
*
* @param str1 string
* @param str2 string
* @return 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 i=0;i<=m;i++) dp[i][0]=i;
// for(int j=1;j<=n;j++) dp[0][j]=j;
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];
//dp[i-1][j-1]--->
//dp[i-1][j],dp[i][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];
// write code here
}
};

C++ 解法, 执行用时: 5ms, 内存消耗: 464KB, 提交时间: 2022-07-24

class Solution {
public:
/**
*
*
*
* @param str1 string
* @param str2 string
* @return int
*/
int editDistance(string str1, string str2) {
// write code here
int len1 = str1.size(), len2 = str2.size(), left_up;
// vector<vector<int>> dp(len1 + 1, vector<int> (len2 + 1, 1001)); // dp[i][j] str1istr2j
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:
/**
*
*
*
* @param str1 string
* @param str2 string
* @return int
*/
int editDistance(string str1, string str2) {
// write code here
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:
/**
*
*
*
* @param str1 string
* @param str2 string
* @return int
*/
int editDistance(string str1, string str2) {
// write code here
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:
/**
*
*
*
* @param str1 string
* @param str2 string
* @return int
*/
int editDistance(string str1, string str2) {
// write code here
//dp[i][j] str1istr2j
// int n1 = str1.length();
// int n2 = str2.length();
// vector<vector<int>> dp(n1+1, vector<int>(n2+1,0));
// for(int i = 1; i <= n1; i++){
// dp[i][0] = dp[i-1][0]+1;
// }
// for(int j = 1; j <= n2; ++j){
// dp[0][j] = dp[0][j-1] +1;
// }
// for(int i = 1; i <= n1; ++i){
// for(int j = 1; j <= n2; ++j){
// if(str1[i-1] == str2[j-1]){
// dp[i][j] = dp[i-1][j-1];
// }else{
// dp[i][j] = min(dp[i-1][j-1] , min(dp[i-1][j], dp[i][j-1])) + 1;
// }
// }
// }
// return dp[n1][n2];
//
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;
// vector<vector<int>> dp(2, vector<int>(n2+1, 0));
for(int j = 1; j <= n2; ++j){
//str1str2str2
dp[0][j] = j;
}
for(int i = 1; i <= n1; ++i){
//str2str1str1
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];
}
};

上一题