[编程题]最小编辑代价
- 热度指数：3356 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。
输入描述:
输出三行，第一行和第二行均为一行字符串，分别表示两个字符串str1，str2。。第三行为三个正整数，代表ic，dc和rc。（1<=ic<=10000、1<=dc<=10000、1<=rc<=10000）
输出描述:
输出一个整数，表示编辑的最小代价。
示例1
输入
abc adc 5 3 2
输出
2
示例2
输入
abc adc 5 3 100
输出
8
示例3
输入
abc abc 5 3 2
输出
0
备注:
时间复杂度，空间复杂度
。(n,m代表两个字符串长度)
经典的动态规划解法，记dp[i][j]表示将str10~i编辑成str20~j的代价，如果str1i=str2j，那么dp[i][j]就可以直接从dp[i-1][j-1]转移过来，否则就比较插入、删除和替换三种操作哪种的代价小：
- 如果str10~i-1已经编辑成了str20~j-1，只需要将str1i替换为str2j可以完成转换，代价为dp[i-1][j-1]+rc
- 如果str10~i-1已经被编辑为str20~j，只需要将str10~i删除一个str1i就可以完成转换，代价为dp[i-1][j]+dc
- 如果str10~i已经被编辑为str20~j-1，只需要插入一个str2j就可以完成转换，代价为dp[i][j-1]+ic
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
char[] str1 = br.readLine().toCharArray();
char[] str2 = br.readLine().toCharArray();
String[] params = br.readLine().split(" ");
int ic = Integer.parseInt(params[0]), dc = Integer.parseInt(params[1]), rc = Integer.parseInt(params[2]);
int[][] dp = new int[str1.length + 1][str2.length + 1];
for(int i = 1; i <= str1.length; i++) dp[i][0] = dp[i - 1][0] + dc; // str1[:i]变成空串
for(int j = 1; j <= str2.length; j++) dp[0][j] = dp[0][j - 1] + ic; // 空串变成str2[:i]
for(int i = 1; i <= str1.length; i++){
for(int j = 1; j <= str2.length; j++){
if(str1[i - 1] == str2[j - 1]){
dp[i][j] = dp[i - 1][j - 1]; // 直接转移过来
}else{
// 比较三种操作哪种代价小
dp[i][j] = Math.min(dp[i - 1][j - 1] + rc, Math.min(dp[i - 1][j] + dc, dp[i][j - 1] + ic));
}
}
}
System.out.println(dp[str1.length][str2.length]);
}
}
发表于 2021-11-27 23:12:07
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
string s1, s2;
int ic, dc, rc, s=0;
cin>>s1>>s2>>ic>>dc>>rc;
if(s1.length()<s2.length()){
swap(ic, dc);
swap(s1, s2);
}
int n=s1.length(), m=s2.length(), dp[m+1];
memset(dp, 0, sizeof(dp));
if(n && m){
for(int i=1;i<=m;i++)
dp[i] = i*ic;
for(int i=1;i<=n;i++){
int k = dp[0];
dp[0] = dc*i;
for(int j=1;j<=m;j++){
int t = dp[j];
if(s1[i-1]==s2[j-1])
dp[j] = k;
else
dp[j] = k + rc;
dp[j] = min(dp[j], dp[j-1]+ic);
dp[j] = min(dp[j], t+dc);
k = t;
}
}
}
cout<<dp[m]<<endl;
return 0;
}
编辑于 2020-03-04 00:17:36
回复(0)
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s1,s2;
cin>>s1>>s2;
int ic,dc,rc;
cin>>ic>>dc>>rc;
if(s1.size()==0||s2.size()==0)
{
cout<<0<<endl;
return 0;
}
string ls = s1.size() >= s2.size() ? s1 : s2;
string ss = s1.size() < s2.size() ? s1 : s2;
if (s1.size() < s2.size()){
int tmp = ic;
ic = dc;
dc = tmp;
}
vector<int>dp(ss.size() + 1);
for (int i = 1; i <= ss.size(); i++)
dp[i] = ic*i;
for (int i = 1; i <= ls.size(); i++){
int pre = dp[0];
dp[0] = dc*i;
for (int j = 1; j <= ss.size(); j++){
int tmp = dp[j];
if (ls[i - 1] == ss[j - 1])
dp[j] = pre;
else
dp[j] = pre + rc;
dp[j] = min(dp[j], dp[j - 1] + ic);
dp[j] = min(dp[j], tmp + dc);
pre = tmp;
}
}
cout<<dp[ss.size()];
return 0;
}
发表于 2019-08-31 21:15:02
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String str1 = sc.nextLine().trim();
String str2 = sc.nextLine().trim();
String[] s = sc.nextLine().trim().split(" ");
int ic=Integer.parseInt(s[0]);
int dc=Integer.parseInt(s[1]);
int rc=Integer.parseInt(s[2]);
int res=new Solution().getMinCost(str1,str2,ic,dc,rc);
System.out.println(res);
}
}
}
class Solution {
public int getMinCost(String str1,String str2,int ic,int dc,int rc){
int[][] dp=new int[str1.length()][str2.length()];
boolean flag=false;
for (int i = 0; i < str1.length(); i++) {
if(!flag&&str1.charAt(i)==str2.charAt(0)) flag=true;
if(flag){
dp[i][0]=i*dc;
}else{
dp[i][0]=Math.min(i*dc+rc,(i+1)*dc+ic);
}
}
flag=false;
for (int i = 0; i < str2.length(); i++) {
if(!flag&&str2.charAt(i)==str1.charAt(0)) flag=true;
if(flag){
dp[0][i]=i*ic;
}else{
dp[0][i]=Math.min(i*ic+rc,(i+1)*ic+dc);
}
}
for (int i = 1; i < str1.length(); i++) {
for (int j = 1; j < str2.length(); j++) {
if(str1.charAt(i)==str2.charAt(j)){
dp[i][j]=dp[i-1][j-1];
}else{
dp[i][j]=Math.min(dp[i-1][j]+dc,dp[i][j-1]+ic);
dp[i][j]=Math.min(dp[i][j],dp[i-1][j-1]+rc);
dp[i][j]=Math.min(dp[i][j],dp[i-1][j-1]+ic+dc);
}
}
}
return dp[str1.length()-1][str2.length()-1];
}
}
发表于 2022-05-09 15:11:12
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.nextLine();
String str2 = sc.nextLine();
int ic = sc.nextInt();
int dc = sc.nextInt();
int rc = sc.nextInt();
System.out.println(minCount(str1, str2, ic, dc, rc));
}
public static int minCount(String str1, String str2, int ic, int dc, int rc) {
int len1 = str1.length();
int len2 = str2.length();
int[][] dp = new int[len1 + 1][len2 + 1];
dp[0][0] = 0;
for (int j = 1; j <= len2; j++) {
dp[0][j] = j * ic;
}
for (int i = 1; i <= len1; i++) {
dp[i][0] = i * dc;
}
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = min(dp[i - 1][j - 1] + rc, dp[i - 1][j] + dc, dp[i][j - 1] + ic);
}
}
return dp[len1][len2];
}
public static int min(int a, int b, int c) {
int temp = a;
if (b < temp) temp = b;
if (c < temp) temp = c;
return temp;
}
}
编辑于 2021-03-19 20:33:50
回复(0)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char str1[5010],str2[5010];
int dp[5010][5010];
int w[3];
int main(){
while(scanf("%s %s",str1,str2)!=EOF){
int len1=strlen(str1);
int len2=strlen(str2);
fill(dp[0],dp[0]+5010*5010,0);
dp[0][0]=0;
for(int i=1;i<=3;++i){
scanf("%d",&w[i]);
}
for(int i=1;i<=len2;++i){
dp[0][i]=w[1]*i;
}
for(int i=1;i<=len1;++i){
dp[i][0]=w[2]*i;
}
for(int i=1;i<=len1;++i){
for(int j=1;j<=len2;++j){
if(str1[i-1]==str2[j-1])
dp[i][j]=dp[i-1][j-1];
else{
dp[i][j]=dp[i-1][j-1]+w[3];
}
dp[i][j]=min(dp[i][j-1]+w[1],min(dp[i-1][j]+w[2],dp[i][j]));
}
}
printf("%d\n",dp[len1][len2]);
}
}
编辑于 2020-04-02 22:17:04
回复(0)
相比LeetCode 72，Edit Distance，本题最关键点在于对备忘录的初始化部分。
- 当 s1 为空串，那么 s1 编辑为 s2 的代价为 i * ic，i 为索引
- 当 s2 为空串，那么 s1 编辑为 s2 的代价为 i * dc，i 为索引
还有就是如果 dc + ic < rc，那么 rc = dc + ic
#include <vector>
(721)#include <string>
#include <iostream>
int editDistance(std::string& s1, std::string& s2,
std::vector<std::vector<int>>& memo,
int i, int j, int rc, int ic, int dc){
if(memo[i][j] != INT32_MAX)
return memo[i][j];
if(s1[i - 1] == s2[j - 1]){
memo[i][j] = editDistance(s1, s2, memo, i - 1, j - 1, rc, ic, dc);
}
else{
int r1 = editDistance(s1, s2, memo, i - 1, j - 1, rc, ic, dc) + rc;
int r2 = editDistance(s1, s2, memo, i, j -1, rc, ic, dc) + ic;
int r3 = editDistance(s1, s2, memo, i - 1, j, rc, ic, dc) + dc;
int temp = std::min(r1, r2);
memo[i][j] = std::min(temp, r3);
}
return memo[i][j];
}
int main(){
std::string s1;
std::string s2;
int ic, dc, rc;
std::cin >> s1;
std::cin >> s2;
std::cin >> ic >> dc >> rc;
std::vector<int> temp(s2.size() + 1, INT32_MAX);
std::vector<std::vector<int>> memo(s1.size() + 1, temp);
memo[0][0] = 0;
for(int i = 1; i <= s1.size(); i++){
memo[i][0] = i * dc;
}
for(int i = 1; i <= s2.size(); i++){
memo[0][i] = i * ic;
}
int res = editDistance(s1, s2, memo, s1.size(), s2.size(),
rc, ic, dc);
std::cout << res << std::endl;
return 0;
}
发表于 2020-03-15 16:41:47
回复(0)
有个问题，为什么不可以像注释那一行的那样，s[i]、s[j]不相等的时候，先删除后插入呢？（即存在 dc + ic < rc情况）
所以个人认为注释的那一行才是正确的解法，虽然都可以通过用例。。。
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s1;
string s2;
int ic, dc, rc;
cin >> s1;
cin >> s2;
cin >> ic >> dc >> rc;
//dp[i][j] s1 s2分别以 s1[i] s2[j] 结尾的字符串编辑代价
vector<vector<int> > dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));
//0表示为空
dp[0][0] = 0;
for(int i = 1; i <= s1.size(); ++i) {
dp[i][0] = i * dc;
}
for(int i = 1; i <= s2.size(); ++i) {
dp[0][i] = i * ic;
}
for(int i = 1; i <= s1.size(); ++i) {
for(int j = 1; j <= s2.size(); ++j) {
if(s1[i-1] != s2[j-1]) {
dp[i][j] = dp[i - 1][j - 1] + rc;
//dp[i][j] = min(dp[i - 1][j - 1] + rc, dp[i - 1][j - 1] + dc + ic);
}
else {
dp[i][j] = dp[i - 1][j - 1];
}
dp[i][j] = min(min(dp[i - 1][j] + dc, dp[i][j - 1] + ic), dp[i][j]);
}
}
cout << dp[s1.size()][s2.size()] << endl;
return 0;
}
编辑于 2020-02-14 21:32:25
回复(1)
#include<iostream>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
string a,b;
int dp[6000][6000];
int x,y,z;
int main()
{cin>>a>>b;//a变成b；
cin>>x>>y>>z;//插入 删除 替换
for(int i=0;i<=b.length();i++)
dp[0][i]=i*x;
for(int i=0;i<=a.length();i++)
dp[i][0]=i*y;
for(int i=1;i<=a.length();i++)
{for(int j=1;j<=b.length();j++)
{if(a[i-1]==b[j-1])
dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j]+y,dp[i][j-1]+x));
else
dp[i][j]=min(dp[i-1][j-1]+z,min(dp[i-1][j]+y,dp[i][j-1]+x));
}
}
cout<<dp[a.length()][b.length()];
} https://blog.csdn.net/weixin_30505043/article/details/97092903 可以参考这篇博客
发表于 2020-02-09 18:17:06
回复(0)
所以python是无论如何都过不了了？一直提示：您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
def distance(str1, str2, ic, dc, rc):
len1, len2 = len(str1) + 1, len(str2) + 1
dp = [0]
for i in range(1, len2):
dp.append(dp[i-1] + ic)
#print(dp)
for i in range(1, len1):
last = dp[0]
dp[0] = i * dc
for j in range(1, len2):
tmp = dp[j]
dp[j] = min(dp[j] + dc, dp[j-1] + ic)
if str1[i - 1] == str2[j - 1]:
dp[j] = min(dp[j], last)
else:
dp[j] = min(dp[j], last + rc)
last = tmp
#print(dp)
return dp[-1]
if __name__ == '__main__':
try:
str1 = input()
str2 = input()
ic, dc, rc = map(int, input().split())
if not str1&nbs***bsp;len(str1) > 5000:
print('0')
if not str2&nbs***bsp;len(str2) > 5000:
print('0')
if ic == 0&nbs***bsp;dc == 0&nbs***bsp;rc == 0&nbs***bsp;ic > 10000&nbs***bsp;dc > 10000&nbs***bsp;rc > 10000:
print('0')
print(distance(str1, str2, ic, dc, rc))
except:
pass
发表于 2019-12-22 00:09:20
回复(1)
问题信息
通过挑战的用户
查看代码-
2022-10-11 17:04:48 -
2022-10-02 21:06:30
-
2022-09-25 10:13:48
-
2022-09-20 19:26:36
-
2022-09-11 15:15:23
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
