Tổng số xóa ASCII tối thiểu cho hai chuỗi trong C ++

Giả sử chúng ta có hai từ w1 và w2, chúng ta phải tìm tổng ASCII thấp nhất của các ký tự đã xóa để 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 sợi dây. Vì vậy, nếu đầu vào giống như “sea” và “eat”, thì đầu ra sẽ là 231, 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. Xóa ‘t’ khỏi “eat” sẽ thêm 116 vào tổng và cuối cùng, cả hai chuỗi đều giống nhau và 115 + 116 =231 là tổng tối thiểu có thể đạt được để đạt được điều này.

Để 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] + s2 [i]
• for i:=1 to n
  • dp [i, 0]:=dp [i - 1, 0] + s1 [i]
• 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 minimumDeleteSum(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] + s2[i];
      }
      for(int i = 1; i <= n; i++){
         dp[i][0] = dp[i - 1][0] + s1[i];
      }
      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] + s1[i], dp[i][j - 1] + s2[j]);
            }
         }
      }
      return dp[n][m];
   }
};
main(){
   Solution ob;
   cout << (ob.minimumDeleteSum("sea", "eat"));
}

Đầu vào

"sea"
"eat"

Đầu ra

231