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

本文主要是介绍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++ 字符串编辑距离代价计算的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---