Khoảng cách chỉnh sửa (Edit Distance) trong C++

Cho hai từ word1 và word2. Tìm số phép toán tối thiểu để biến word1 thành word2. Ba phép toán: chèn, xóa, thay thế ký tự. Ví dụ: "evaluate" và "fluctuate" → kết quả 5.

Giải thuật (Quy hoạch động)

• n = độ dài w1, m = độ dài w2.
• Tạo mảng dp kích thước (n+1) x (m+1).
• Khởi tạo: dp[i][0] = i, dp[0][j] = j.
• Thêm khoảng trắng đầu chuỗi w1, w2.
• Với i từ 1 đến n, j từ 1 đến m:
  • Nếu w1[i] != w2[j]: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
  • Ngược lại: dp[i][j] = dp[i-1][j-1].
• Trả về dp[n][m].

Ví dụ minh họa (C++)

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

class Solution {
public:
    int minDistance(string w1, string w2) {
        int n = w1.size();
        int m = w2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= m; j++) {
                if(i == 0) dp[i][j] = j;
                else if(j == 0) dp[i][j] = i;
            }
        }
        w1 = " " + w1;
        w2 = " " + w2;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(w1[i] != w2[j]) {
                    dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
                } else {
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }
        return dp[n][m];
    }
};

int main() {
    Solution ob;
    cout << (ob.minDistance("fluctuate", "evaluate"));
    return 0;
}

Đầu vào

"fluctuate" "evaluate"

Đầu ra

5