Minimum ASCII Delete Sum for Two Strings ใน C++

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

ลบ 's' จาก s1 → "ea" (ASCII 115)

ลบ 't' จาก s2 → "ea" (ASCII 116)

ผลรวม = 115 + 116 = 231

อัลกอริทึม: Dynamic Programming (DP)

คล้ายกับปัญหา Edit Distance / Longest Common Subsequence (LCS) แต่ค่าใช้จ่าย (cost) คือค่า ASCII ของตัวอักษรที่ลบ

กำหนด dp[i][j] = ค่า ASCII delete sum ต่ำสุดเพื่อให้ s1[0..i-1] และ s2[0..j-1] เหมือนกัน

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

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

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

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

class Solution {
public:
    int minimumDeleteSum(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] = dp[0][i-1] + (int)s2[i];
        for (int i = 1; i <= n; i++)
            dp[i][0] = dp[i-1][0] + (int)s1[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] + (int)s1[i], dp[i][j-1] + (int)s2[j]);
                }
            }
        }
        return dp[n][m];
    }
};

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

Input

"sea" "eat"

Output

231

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

• เวลา: O(n × m)
• พื้นที่: O(n × m) (สามารถลดเหลือ O(min(n,m)) ได้ด้วยการใช้ 1D array)

หมายเหตุ: โค้ดต้นฉบับมีบั๊กในบรรทัด dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1) ควรเป็นบวกค่า ASCII ของตัวอักษร ไม่ใช่บวก 1 ได้แก้ไขแล้วในตัวอย่างนี้