Delete Operations for Two Strings ใน C++

ตัวอย่าง: s1 = "sea", s2 = "eat"

ลบ 's' จาก s1 → "ea"

ลบ 't' จาก s2 → "ea"

จำนวนขั้นตอน = 2

อัลกอริทึม: Dynamic Programming (คล้าย Edit Distance / LCS)

กำหนด dp[i][j] = จำนวนการลบขั้นตอนน้อยสุดเพื่อให้ s1[0..i-1] และ s2[0..j-1] เหมือนกัน

ความสัมพันธ์แบบเวียนเกิด (Recurrence):

• Base case: dp[0][j] = j (ลบทั้งหมด j ตัวจาก s2), dp[i][0] = i (ลบทั้งหมด i ตัวจาก s1)
• Transition:
  • หาก s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] (ไม่ต้องลบ)
  • หากไม่เท่ากัน: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1 (ลบจาก s1 หรือ s2)

สังเกต: ต่างจาก Minimum ASCII Delete Sum (โจทย์ก่อนหน้า) ที่ cost = ASCII value ที่นี่ cost = 1 (นับจำนวนการลบ)

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

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minDistance(string s1, string s2) {
        int n = s1.size();
        int m = s2.size();
        
        // เพิ่มช่องว่างหน้าสตริงเพื่อให้ index ตรงกับ dp (1-based)
        s1 = " " + s1;
        s2 = " " + s2;
        
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        
        // Base cases
        for (int i = 1; i <= m; i++)
            dp[0][i] = i;
        for (int i = 1; i <= n; i++)
            dp[i][0] = i;
        
        // Fill DP table
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1[i] == s2[j]) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;
                }
            }
        }
        return dp[n][m];
    }
};

int main() {
    Solution ob;
    cout << ob.minDistance("sea", "eat") << endl;
    return 0;
}

Input

"sea" "eat"

Output

2

ความซับซ้อน (Complexity)

• เวลา: O(n × m)
• พื้นที่: O(n × m) (ลดเหลือ O(min(n,m)) ได้)

ความสัมพันธ์กับ LCS: จำนวนการลบขั้นตอนน้อยสุด = len(s1) + len(s2) - 2 * LCS(s1, s2) เพราะตัวอักษรที่ร่วมกัน (LCS) ไม่ต้องลบ ตัวอื่นต้องลบทั้งหมด

แก้ไขจากโค้ดต้นฉบับ: โค้ดต้นฉบับมีบรรทัด vector<int> v = {1,1,1}; ที่ไม่ได้ใช้ และ dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1) เขียนซ้ำ +1 ได้ลดรูปเป็น min(...) + 1 แล้ว