พิมพ์วิธีแปลงสตริงหนึ่งเป็นอีกสตริงหนึ่ง (Edit Distance) ใน C++

บทนำ

โจทย์: หาวิธีแปลง str1 เป็น str2 ด้วยการ Insert, Remove, Replace พิมพ์ลำดับขั้นตอน (หนึ่งวิธีที่เป็นไปได้)

แนวทางแก้ปัญหา

1. สร้างตาราง DP[i][j] = minimum edits จาก str1[0..i-1] เป็น str2[0..j-1]
2. DP[i][j] = DP[i-1][j-1] ถ้า str1[i-1]==str2[j-1]
3. DP[i][j] = 1 + min(DP[i-1][j-1], DP[i-1][j], DP[i][j-1]) ถ้าไม่เท่ากัน
4. Backtrack จาก DP[len1][len2] ไป DP[0][0] พิมพ์ operation ตามเส้นทาง

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

int DP[100][100];

void findWays(string str1, string str2) {
    int len1 = str1.length();
    int len2 = str2.length();
    int i, j;
    DP[len1 + 1][len2 + 1];
    for (i = 0; i <= len1; i++) DP[i][0] = i;
    for (j = 0; j <= len2; j++) DP[0][j] = j;
    for (i = 1; i <= len1; i++) {
        for (j = 1; j <= len2; j++) {
            if (str1[i - 1] == str2[j - 1])
                DP[i][j] = DP[i - 1][j - 1];
            else
                DP[i][j] = (min(min(DP[i - 1][j - 1], DP[i - 1][j]), DP[i][j - 1])) + 1;
        }
    }
    while (len1 && len2) {
        if (str1[len1 - 1] == str2[len2 - 1]) {
            len1--; len2--;
        } else if (DP[len1][len2] == DP[len1 - 1][len2 - 1] + 1) {
            cout << "\nModify '" << str1[len1 - 1] << "' to '" << str2[len2 - 1];
            len1--; len2--;
        } else if (DP[len1][len2] == DP[len1 - 1][len2] + 1) {
            cout << "\nRemove " << str1[len1 - 1] << "'";
            len1--;
        } else if (DP[len1][len2] == DP[len1][len2 - 1] + 1) {
            cout << "\nInsert '" << str2[len2 - 1] << "'";
            len2--;
        }
    }
}

int main() {
    string str1 = "kfeodge";
    string str2 = "kfcadqpe";
    cout << "Way to convert one string into another string is ";
    findWays(str1, str2);
    return 0;
}

ผลลัพธ์

Way to convert one string into another string is
Modify 'g' to 'p
Insert 'q'
Modify 'o' to 'a
Modify 'e' to 'c

หมายเหตุ

โค้ดนี้พิมพ์ได้เพียงหนึ่งวิธี (One Possible Way) การพิมพ์ทุกวิธี (All Ways) ต้องใช้โครงสร้างข้อมูลซับซ้อนกว่า (Vector of Strings) และซับซ้อนกว่านี้มาก

สรุป

Edit Distance (Levenshtein Distance) + Backtracking แสดงขั้นตอนการแปลงสตริง ใช้ใน Diff Tools, DNA Alignment, Spell Checkers