C++を使用して1つの文字列を別の文字列に変換するための削除と挿入の最小数。

説明

それぞれサイズmとnの2つの文字列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