C++ 修改字符串的最小成本

在本教程中，我们使用C ++编程概念来实现示例，以找到将字符串修改为另一个字符串的最小成本。字符串修改包括将字符串更改为另一个字符串的操作。字符串操作包括插入、删除和替换。我们预定义了每个操作的成本。您可以选择所需的成本值。通过计算字符串修改的总操作成本生成输出。

插入函数用于插入丢失的字符，删除用于删除不需要的字符，替换操作用于将一个字符替换为另一个字符。

为了实现上述任务，我们使用了两个逻辑：

动态规划： 将程序划分为子部分可以减少时间和复杂性。
递归函数调用： 重复调用一个函数，直到任务完成。

示例1

String1 = “book”
String2 = “back”
costInsertion = 1
costDeletion = 1
costSubstitution = 2

输出

在上述示例中，使用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

在上述演示中，通过插入、删除和替换三种操作，将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是第二个字符串的长度。
迭代输入字符串的每个字符，检查是否需要特定操作，并根据字符串2的要求执行操作。
返回字符串修改操作的总最小成本。

示例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;
}