使用C ++将一个字符串转换为另一个字符串的最小删除和插入次数。
描述
给定两个分别为m和n的字符串str1和str2。任务是从str1中/在str1中删除并插入最少数量的字符，以便将其转换为str2。
Str1 = “nhooo” 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("nhooo", "tutorials");
return 0;
}输出结果
当您编译并执行上述程序时。它生成以下输出-
Min deletion = 5 Min insertion = 0
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短