C++를 사용하여 한 문자열을 다른 문자열로 변환하기 위한 최소 삭제 및 삽입 횟수입니다.

설명

각각 크기가 m 및 n인 두 개의 문자열 str1 및 str2가 제공됩니다. 작업은 str2로 변환하기 위해 str1에서/에서 최소 문자 수를 삭제하고 삽입하는 것입니다.

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