Số lần xóa và chèn tối thiểu để biến đổi chuỗi này thành chuỗi kia bằng C++

Mô tả

Cho hai chuỗi str1 và str2 kích thước m và n tương ứng. Nhiệm vụ là xóa và chèn số lượng ký tự tối thiểu từ/vào str1 để biến nó thành str2.

Str1 = "tutorialspoint" Str2 = "tutorials" Để biến str1 thành str2 ta phải xóa 5 ký tự là "point" từ str1.

Thuật toán

1. Tìm dãy con chung dài nhất (LCS) của str1 và str2. Gọi nó là "lcsSize" 2. Số ký tự cần xóa = (độ dài str1 - lcsSize) 3. Số ký tự cần chèn = (độ dài str2 - lcsSize)

Ví dụ

#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; }

Kết quả

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:

Min deletion = 5 Min insertion = 0