Thao tác xóa đối với hai chuỗi trong C ++

Giả sử chúng ta có hai từ w1 và w2, chúng ta phải tìm số bước tối thiểu cần thiết để làm cho w1 và w2 giống nhau, trong đó mỗi bước chúng ta có thể xóa một ký tự trong một trong hai chuỗi . Vì vậy, nếu đầu vào giống như “sea” và “eat”, thì đầu ra sẽ là 2, vì chúng ta cần xóa ‘s’ khỏi w1, đây sẽ là “ea” và xóa “t” khỏi “eat” khỏi w2. Sau đó, chúng giống nhau.

Để 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 s1, m:=kích thước của s2
• thêm một khoảng trống trước các chuỗi s1 và s2, sau đó cập nhật s1 và s2 cho phù hợp
• tạo một bảng có kích thước (n + 1) x (m + 1)
• for i:=1 to m
  • dp [0, i]:=dp [0, i - 1] + 1
• for i:=1 to n
  • dp [i, 0]:=dp [i - 1, 0] + 1
• cho tôi trong phạm vi từ 1 đến n
  • cho j trong phạm vi từ 1 đến m
    • nếu s1 [i] =s2 [j]
      • dp [i, j]:=dp [i - 1, j - 1]
    • else dp [i, j] =tối thiểu là dp [i - 1, j] + 1 và dp [i, j - 1] + 1
• trả về dp [n, m]

Ví dụ (C ++)

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 s1, string s2) {
      int n = s1.size();
      int m = s2.size();
      s1 = " " + s1;
      s2 = " " + s2;
      vector < vector <int> > dp(n + 1, vector <int>(m + 1));
      for(int i = 1; i <= m; i++){
         dp[0][i] = dp[0][i - 1] + 1;
      }
      for(int i = 1; i <= n; i++){
         dp[i][0] = dp[i - 1][0] + 1;
      }
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= m; j++){
            if(s1[i] == s2[j]){
               dp[i][j] = dp[i - 1][j - 1];
            }
            else{
               dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
            }
         }
      }
      return dp[n][m];
   }
};
main(){
   Solution ob;
   vector<int> v = {1,1,1};
   cout << (ob.minDistance("sea", "eat"));
}

Đầu vào

"sea"
"eat"

Đầu ra

2