Chương trình tìm khoảng cách chỉnh sửa nhỏ nhất giữa hai chuỗi trong C ++

Giả sử chúng ta có hai từ S và T, chúng ta phải tìm số phép toán tối thiểu cần thiết để chuyển đổi từ S sang T. Các phép toán có thể có ba loại, đây là

• chèn một ký tự,
• xóa một ký tự
• thay thế một ký tự.

Vì vậy, nếu các chuỗi đầu vào là "đánh giá" và "dao động", thì kết quả sẽ là 5.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của s, m:=kích thước của t,

• tạo một mảng dp có kích thước n + 1

• cho tôi trong phạm vi từ 0 đến n

  • dp [i]:=mảng mới có kích thước m + 1

  • cho j trong phạm vi từ 0 đến m:

    • dp [i, j]:=0

    • nếu i =0, thì dp [i, j] =j

    • ngược lại khi j =0 thì dp [i, j]:=i

• s:=khoảng trắng và nối s, t:=khoảng trắng và nối t

• cho tôi trong phạm vi từ 1 đến n

  • đối với j trong phạm vi từ 1 đến m

    • nếu s [i] không phải là t [j], thì dp [i, j]:=1 + min của dp [i - 1, j], dp [i, j - 1], dp [i - 1, j - 1]

    • nếu không thì dp [i, j]:=dp [i - 1, j - 1]

• trả về dp [n, m]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minDistance(string s, string t) {
      int n = s.size();
      int m =t.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;
         }
      }
      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];
   }
};
main(){
   Solution ob;
   cout << (ob.minDistance("fluctuate", "evaluate"));
}

Đầu vào

"fluctuate"
"evaluate"

Đầu ra

5