数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究修改字符串的最小成本
介绍
在本教程中，我们使用 C++ 编程概念实现示例，以查找修改字符串的最小成本。字符串修改包括将一个字符串更改为另一个字符串的操作。字符串操作包括插入、删除和替换。我们预定义了每个操作的成本。您可以选择您选择的成本值。通过计算字符串修改的总操作成本来生成输出。
插入函数用于插入缺失的字符，删除用于删除不需要的字符，替换操作用于将一个字符替换为另一个字符。
为了实现上述任务，我们使用两种逻辑
动态规划：将程序分成子部分可以减少时间和复杂度。
递归函数调用：重复调用函数，直到任务完成。
演示 1
String1 = “book” String2 = “back” costInsertion = 1 costDeletion = 1 costSubstitution = 2
输出
4
在上面的演示中，使用 3 种不同的操作 (costInsertion、costDeletion、costSubstitution) 将 string1 修改为 string2；这些操作定义了使用每个操作的成本。插入新元素的成本为 1。删除已存在元素的成本为 1，用新元素替换元素的成本为 2。每个操作的成本都是预定义的。使用该操作，将 string1 转换为 string2 的成本为 2，其中包括将“o”替换为“a”和“o”替换为“c”。
演示 2
String1 = “abcdef” String2 = “azced” costInsertion = 1 costDeletion = 1 costSubstitution = 1
输出
Minimum string modification cost is 5
在上面的演示中，使用 3 种操作：插入、删除和替换将 string1 修改为 string2。每个操作的成本都是预定义的。将 string1 转换为 string2 的总成本为 5，其中包括删除“b”、“d”和“f”，插入“z”和“d”的操作。
示例中使用的 C++ 库函数
语法
length()：此内置库函数在<string>头文件中定义。它以字符总数的形式返回字符串长度。
string_name.length();
vector()：它在
vector<data_type> vector_name;
算法
获取两个输入字符串。
定义每个操作的成本。
创建一个 (m+1)x (n+1) 的二维数组，其中 m 是第一个字符串的长度，n 是第二个字符串的长度。
遍历输入字符串的每个字符，以检查对特定操作的需求，并根据 string2 的要求执行操作。
返回字符串修改操作的最小总成本。
示例 1
我们使用递归实现了一个演示。minimumCost() 函数计算将 string1 修改为 string2 的最小成本。该函数考虑 3 种情况：当其中一个字符串为空时，使用插入/删除操作，返回它们中的最小值。
#include <iostream>
#include <algorithm>
using namespace std;
int minimumCost(string str1, string str2, int insertionCost, int deletionCost, int substitutionCost, int x, int y)
{
if (x == 0)
{
return y * insertionCost;
}
if (y == 0)
{
return x * deletionCost;
}
if (str1[x - 1] == str2[y - 1])
{
return minimumCost(str1, str2, insertionCost, deletionCost, substitutionCost, x - 1, y - 1);
}
// Recursively calculating the operation cost
int cd = deletionCost + minimumCost(str1, str2, insertionCost, deletionCost, substitutionCost, x - 1,
y);
int ci = insertionCost + minimumCost(str1, str2, insertionCost, deletionCost, substitutionCost, x, y - 1);
int cs = substitutionCost + minimumCost(str1, str2, insertionCost, deletionCost, substitutionCost, x - 1, y - 1);
return min({cd, ci, cs});
}
int main() {
string str1 = "kitten";
string str2 = "sitting";
int insertionCost = 1;
int deletionCost = 1;
int substitutionCost = 2;
int m = minimumCost(str1, str2, insertionCost, deletionCost, substitutionCost, str1.length(), str2.length());
cout << "Minimum cost to modify the string: " << m << endl;
return 0;
}
输出
Minimum cost to modify the string : 5
示例 2
我们使用动态规划实现了一个演示。递归方法的时间复杂度很高，对于大型输入并不实用。动态规划效率更高，因为它将问题分解成块。
创建了一个 minimumCost() 函数和数组 dp 来迭代字符串的每个字符。使用 length() 函数查找输入字符串的长度。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//user-defined function to calculate the minimum cost
int minimumCost(string str1, string str2, int insertionCost, int deletionCost, int substitutionCost)
{
int a = str1.length();
int b = str2.length();
vector<vector<int>> dp(a + 1, vector<int>(b + 1, 0));
for (int x = 0; x <= a; x++)
{
dp[x][0] = x * deletionCost;
}
for (int y = 0; y <= b; y++)
{
dp[0][y] = y * insertionCost;
}
for (int x = 1; x <= a; x++)
{
for (int y = 1; y <= b; y++)
{
if (str1[x - 1] == str2[y - 1])
{
dp[x][y] = dp[x - 1][y - 1];
}
else
{
dp[x][y] = min({dp[x - 1][y] + deletionCost,
dp[x][y - 1] + insertionCost,
dp[x - 1][y - 1] + substitutionCost});
}
}
}
// Return the minimum cost in array form
return dp[a][b];
}
int main()
{
string str1 = "kitten";
string str2 = "sitting";
int insertionCost = 1;
int deletionCost = 1;
int substitutionCost = 2;
int mc = minimumCost(str1, str2, insertionCost, deletionCost, substitutionCost);
cout << "Minimum cost to modify the string: " << mc << endl;
return 0;
}
输出
Minimum cost to modify the string. 5
结论
我们完成了本教程，我们使用动态规划和递归方法实现了两个示例。要修改字符串，使用了三种不同的操作：插入、删除和替换。每个操作的成本在示例中是预定义的。
浏览量 265
