資料結構
網路
關係資料庫管理系統 (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
