Delete Operations for Two Strings trong C++

Cho hai chuỗi w1, w2. Tìm số bước xóa ít nhất để hai chuỗi giống nhau. Mỗi bước xóa một ký tự ở một chuỗi.

Ví dụ: "sea" và "eat" → output 2. Xóa 's' từ "sea" và 't' từ "eat".

Giải thuật (DP - LCS biến thể)

• n = s1.size(), m = s2.size().
• Thêm khoảng trắng đầu chuỗi.
• Bảng dp[n+1][m+1].
• Khởi tạo: dp[0][i] = i, dp[i][0] = i.
• Duyệt i=1..n, j=1..m:
  • Nếu s1[i] == s2[j]: dp[i][j] = dp[i-1][j-1].
  • Ngược lại: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1.
• Trả về dp[n][m].

Ví dụ code

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

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

Input

"sea" "eat"

Output

2