使用 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

Narendra Kumar

更新于: 31-Oct-2019

316 视图

开启你的 职业生涯

完成课程获取认证

开始