資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究使用 C++ 將一個字串轉換成另一個字串的最小刪除和插入次數。
說明
給定兩個分別大小為 m 和 n 的字串 str1 和 str2。任務是從 str1 中刪除和插入最小數量的字元以將其轉換成 str2。
Str1 = “tutorialspoint” Str2 = “tutorials” To transform str1 to str2 we have to delete five characters i.e. “point” from str1.
演算法
1. Find longest common subsequence of str1 and str2. Let’s call it as “lcsSize” 2. Number of characters to be deleted = (length of str1 - lcsSize) 3. Number of characters to be inserted = (length of str2 - lcsSize)
示例
#include <iostream>
#include <algorithm>
using namespace std;
int lcs(string s1, string s2, int m, int n){
if (m == 0 || n == 0) {
return 0;
}
if (s1[m - 1] == s2[n - 1]) {
return 1 + lcs(s1, s2, m - 1, n - 1);
} else {
return max(lcs(s1, s2, m, n - 1), lcs(s1, s2, m - 1, n));
}
}
void minDeletionAndInsertion(string s1, string s2){
int m = s1.size();
int n = s2.size();
int lcsSize = lcs(s1, s2, m, n);
cout << "Min deletion = " << (m - lcsSize) << endl;
cout << "Min insertion = " << (n - lcsSize) << endl;
}
int main(){
minDeletionAndInsertion("tutorialspoint", "tutorials");
return 0;
}輸出
編譯並執行上述程式後，它將生成以下輸出 −
Min deletion = 5 Min insertion = 0
更新於: 31-Oct-2019
316 檢視
廣告