จำนวนการลบและแทรกน้อยที่สุดเพื่อแปลงสตริงหนึ่งเป็นอีกสตริงหนึ่งด้วย C++

คำอธิบาย

กำหนดสตริงสองตัว str1 และ str2 ขนาด m และ n ตามลำดับ งานคือลบและแทรกจำนวนตัวอักษรน้อยที่สุดจาก/ใน str1 เพื่อแปลงมันเป็น str2

Str1 = "tutorialspoint" Str2 = "tutorials"
เพื่อแปลง str1 เป็น str2 เราต้องลบ 5 ตัวอักษร คือ "point" จาก str1

อัลกอริทึม

1. หาลำดับย่อยร่วมที่ยาวที่สุด (Longest Common Subsequence) ของ str1 และ str2 ให้เรียกว่า "lcsSize"
2. จำนวนตัวอักษรที่ต้องลบ = (ความยาวของ str1 - lcsSize)
3. จำนวนตัวอักษรที่ต้องแทรก = (ความยาวของ 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