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

Giả sử chúng ta có hai từ word1 và word2, chúng ta phải tìm số phép toán tối thiểu cần thiết để ghép nối từ word1 đến word2. Các hoạt động có thể có ba loại, đó là chèn một ký tự, xóa một ký tự và 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 w1, m:=kích thước của w2,

• 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

• w1:=khoảng trắng và nối w1, w2:=khoảng trắng và nối w2

• 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 w1 [i] không phải là w2 [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]

Ví dụ

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

#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[i1][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