Chỉnh sửa khoảng cách

Có hai chuỗi cho trước. Chuỗi đầu tiên là chuỗi nguồn và chuỗi thứ hai là chuỗi đích. Trong chương trình này, chúng ta phải tìm bao nhiêu chỉnh sửa có thể cần thiết để chuyển đổi chuỗi đầu tiên sang chuỗi thứ hai.

Chỉnh sửa chuỗi có thể là Chèn một số phần tử, xóa nội dung nào đó khỏi chuỗi đầu tiên hoặc sửa đổi nội dung nào đó để chuyển đổi thành chuỗi thứ hai.

Đầu vào và Đầu ra

Input:
Two strings to compare.
string 1: Programming
string 2: Programs
Output:
Enter the initial string: Programming
Enter the final string: Programs
The number of changes required to convert Programming to Programs is 4

Thuật toán

editCount(initStr, finalStr, initLen, finalLen)

Đầu vào - Chuỗi đầu tiên và chuỗi cuối cùng và độ dài của chúng.
Đầu ra - Cần có số lần chỉnh sửa để chuyển initStr thành finalStr.

Begin
   if initLen = 0, then
      return finalLen
   if finalLen := 0, then
      return initLen

   if initStr[initLen - 1] = finalStr[finalLen - 1], then
      return editCount(initStr, finalStr, initLen – 1, finalLen - 1)
   answer := 1 + min of (editCount(initStr, finalStr, initLen , finalLen - 1)),
      (editCount(initStr, finalStr, initLen – 1, finalLen ),
      (editCount(initStr, finalStr, initLen – 1, finalLen - 1)
   return answer
End

Ví dụ

#include<iostream>
using namespace std;

int min(int x, int y, int z) {       //find smallest among three numbers
   if(x < y) {
      if(x < z)
         return x;
      else
         return z;
   }else {
      if(y < z)
         return y;
      else
         return z;
   }
}

int editCount(string initStr , string finalStr, int initLen, intfinalLen) {
   if (initLen == 0)       //when initial string is empty, add all characters of final string
      return finalLen;

   if (finalLen == 0)       //when final string is empty, delete all characters from initial string
      return initLen;

   //when last character matches, recursively check previous characters
   if (initStr[initLen-1] == finalStr[finalLen-1])
      return editCount(initStr, finalStr, initLen-1, finalLen-1);

   //if last character match is not found, check for insert, delete and update operations recursively
   return 1 + min ( editCount(initStr, finalStr, initLen, finalLen- 1),  // insert
 
      editCount(initStr, finalStr, initLen-1, finalLen), // delete
      editCount(initStr, finalStr, initLen-1, finalLen-1) // update
   );
}

int main() {
   string initStr;
   string 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;
   cout << " is " << editCount( initStr , finalStr, initStr.size(), finalStr.size()) << endl;
}

Đầu ra

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