โปรแกรมหาระยะทางแก้ไขขั้นต่ำระหว่างสองสตริงใน C++

สมมติว่าเรามีคำสองคำ S และ T เราต้องหาจำนวนการดำเนินการน้อยที่สุดเพื่อแปลง S ให้เป็น T การดำเนินการมี 3 ประเภท: แทรกตัวอักษร, ลบตัวอักษร, แทนที่ตัวอักษร

เช่น สตริง "evaluate" และ "fluctuate" ผลลัพธ์คือ 5

ขั้นตอนการแก้ปัญหา (Levenshtein Distance)

• n = ความยาว s, m = ความยาว t
• สร้างตาราง dp ขนาด (n+1) x (m+1)
• เริ่มต้น: dp[i][0] = i, dp[0][j] = j
• เพิ่มช่องว่างหน้าสตริงทั้งสอง (ดัชนีเริ่มจาก 1)
• วนลูป i=1..n, j=1..m:
  • ถ้า s[i] != t[j]: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
  • ถ้า s[i] == t[j]: dp[i][j] = dp[i-1][j-1]
• คืนค่า dp[n][m]

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

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

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

อินพุต

"fluctuate" "evaluate"

เอาต์พุต

5