ระยะทางแก้ไข (Edit Distance)

กำหนดสตริง 2 สตริง: สตริงต้นทาง (Source) และสตริงเป้าหมาย (Target) ต้องการหาจำนวนการแก้ไขขั้นต่ำ (Insert, Delete, Replace) เพื่อแปลงสตริงต้นทางเป็นสตริงเป้าหมาย

การรับค่าและแสดงผล

Input: สตริง 1: "Programming", สตริง 2: "Programs"
Output: The number of changes required to convert Programming to Programs is 4

อัลกอริทึม

editCount(initStr, finalStr, initLen, finalLen) - เรียกซ้ำ (Recursive)

Begin
  if initLen = 0 then return finalLen  // ต้อง insert ทั้งหมด
  if finalLen = 0 then return initLen  // ต้อง delete ทั้งหมด
  
  if initStr[initLen-1] = finalStr[finalLen-1] then
    return editCount(initStr, finalStr, initLen-1, finalLen-1)
  
  // ตัวเลือก 3 แบบ: Insert, Delete, Replace
  answer := 1 + min(
    editCount(initStr, finalStr, initLen, finalLen-1),     // Insert
    editCount(initStr, finalStr, initLen-1, finalLen),     // Delete
    editCount(initStr, finalStr, initLen-1, finalLen-1)    // Replace
  )
  
  return answer
End

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

#include <iostream>
using namespace std;

int min(int x, int y, int z) {
  if(x < y) return (x < z) ? x : z;
  else return (y < z) ? y : z;
}

int editCount(string initStr, string finalStr, int initLen, int finalLen) {
  if (initLen == 0) return finalLen;
  if (finalLen == 0) return initLen;
  if (initStr[initLen-1] == finalStr[finalLen-1])
    return editCount(initStr, finalStr, initLen-1, finalLen-1);
  
  return 1 + min(
    editCount(initStr, finalStr, initLen, finalLen-1),   // insert
    editCount(initStr, finalStr, initLen-1, finalLen),   // delete
    editCount(initStr, finalStr, initLen-1, finalLen-1)  // replace
  );
}

int main() {
  string initStr, finalStr;
  cout << "Enter the initial string: "; cin >> initStr;
  cout << "Enter the final string: "; cin >> finalStr;
  cout << "The number of changes required to convert " << initStr 
       << " to " << finalStr << " is " 
       << editCount(initStr, finalStr, initStr.size(), finalStr.size());
}

ผลลัพธ์

Enter the initial string: Programming
Enter the final string: Programs
The number of changes required to convert Programming to Programs is 4