Edit Distance ใน C++

สมมติว่าเรามีคำสองคำคือ word1 และ word2 เราต้องหาจำนวนการดำเนินการขั้นต่ำที่ต้องใช้เพื่อแปลง word1 เป็น word2 การดำเนินการมี 3 ประเภท ได้แก่ เพิ่มตัวอักษร ลบตัวอักษร และแทนที่ตัวอักษร เช่นถ้าสตริงอินพุตคือ "evaluate" และ "fluctuate" ผลลัพธ์จะเป็น 5

ขั้นตอนการแก้ปัญหา

• n := ขนาดของ w1, m := ขนาดของ w2
• สร้างอาร์เรย์ dp ขนาด n + 1
• for i ในช่วง 0 ถึง n
  • dp[i] := อาร์เรย์ใหม่ขนาด m + 1
  • for j ในช่วง 0 ถึง m
    • dp[i, j] := 0
    • ถ้า i = 0 แล้ว dp[i,j] = j
    • มิฉะนั้นถ้า j = 0 แล้ว dp[i, j] := i
• w1 := เว้นวรรคต่อ w1, w2 := เว้นวรรคต่อ w2
• for i ในช่วง 1 ถึง n
  • for j ในช่วง 1 ถึง m
    • ถ้า w1[i] ไม่ใช่ w2[j] แล้ว dp[i, j] := 1 + min ของ dp[i – 1, j], dp[i, j - 1], dp[i – 1, j – 1]
    • มิฉะนั้น dp[i, j] := dp[i – 1, j – 1]
• คืนค่า dp[n, m]

ตัวอย่างโค้ด 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();
        int** dp = new int*[n+1];
        for(int i = 0; i <= n; i++){
            dp[i] = new int[m+1];
            for(int j = 0; j <= m; j++){
                dp[i][j] = 0;
                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"));
}

อินพุต

"fluctuate" "evaluate"

เอาต์พุต

5