C++ 字符串编辑距离代价计算

2024-06-21 08:12

本文主要是介绍C++ 字符串编辑距离代价计算,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

描述

给定两个字符串str1和str2,再给定三个整数ic,dc和rc,分别代表插入、删除和替换一个字符的代价,请输出将str1编辑成str2的最小代价。

数据范围:0≤∣𝑠𝑡𝑟1∣,∣𝑠𝑡𝑟2∣≤50000≤∣str1∣,∣str2∣≤5000,0≤𝑖𝑐,𝑑𝑐,𝑟𝑐≤10000 0≤ic,dc,rc≤10000 

要求:空间复杂度 𝑂(𝑛)O(n),时间复杂度 𝑂(𝑛𝑙𝑜𝑔𝑛)O(nlogn)

示例1

输入:

"abc","adc",5,3,2

复返回值:

2
#include <vector>class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** min edit cost* @param str1 string字符串 the string* @param str2 string字符串 the string* @param ic int整型 insert cost* @param dc int整型 delete cost* @param rc int整型 replace cost* @return int整型*/int minEditCost(string str1, string str2, int ic, int dc, int rc) {// write code hereint m = str1.length();int n = str2.length();//dp[i][j] 表示由str1[0:i-1] 编辑成 str2[0:j-1]的代价std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1,0));//dp[i][0] 表示由str1[0:i-1] 编辑成 str[0:0] 的代价, 需插入 for(int i = 1; i <= m; i++){dp[i][0] = i * dc; //删除的情况}//dp[0][j] 表示由str1[0:0] 编辑成 str[0:j-1] 的代价, 需删除for(int j = 1; j <= n; j++){dp[0][j] = j * ic; //插入的情况}for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(str1[i-1] == str2[j-1]){dp[i][j] = dp[i-1][j-1];}else{// dp[i][j] = dp[i][j-1] + ic; //插入的情况// dp[i][j] = dp[i-1][j] + dc; //删除的情况// dp[i][j] = dp[i-1][j-1] + rc; //替换的情况dp[i][j] = std::min(dp[i-1][j-1] + rc, dp[i][j-1] + ic);dp[i][j] = std::min(dp[i][j], dp[i-1][j] + dc);}}}return dp[m][n];}
};

这篇关于C++ 字符串编辑距离代价计算的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1080674

相关文章

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

poj 1113 凸包+简单几何计算

题意: 给N个平面上的点,现在要在离点外L米处建城墙,使得城墙把所有点都包含进去且城墙的长度最短。 解析: 韬哥出的某次训练赛上A出的第一道计算几何,算是大水题吧。 用convexhull算法把凸包求出来,然后加加减减就A了。 计算见下图: 好久没玩画图了啊好开心。 代码: #include <iostream>#include <cstdio>#inclu

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

uva 11178 计算集合模板题

题意: 求三角形行三个角三等分点射线交出的内三角形坐标。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

XTU 1237 计算几何

题面: Magic Triangle Problem Description: Huangriq is a respectful acmer in ACM team of XTU because he brought the best place in regional contest in history of XTU. Huangriq works in a big compa