ขั้นต่ำ ASCII ลบรวมสำหรับสองสตริงใน C ++

สมมติว่าเรามีคำสองคำ w1 และ w2 เราต้องหาผลรวม ASCII ที่ต่ำที่สุดของอักขระที่ถูกลบเพื่อให้ w1 และ w2 เหมือนกัน โดยในแต่ละขั้นตอน เราสามารถลบอักขระได้หนึ่งตัวใน สตริง ดังนั้นหากอินพุตเป็นเหมือน "ทะเล" และ "กิน" ผลลัพธ์จะเป็น 231 เนื่องจากเราต้องลบ 's' ออกจาก w1 นี่จะเป็น "ea" และลบ "t" จาก "eat" จาก w2 แล้วพวกเขาก็เหมือนกัน การลบ 't' จาก "eat" จะเพิ่ม 116 ให้กับผลรวม และในตอนท้าย สตริงทั้งสองจะเหมือนกัน และ 115 + 116 =231 คือผลรวมขั้นต่ำที่สามารถทำได้

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ s1, m :=ขนาดของ s2
• เพิ่มช่องว่างก่อนสตริง s1 และ s2 จากนั้นอัปเดต s1 และ s2 ตามลำดับ
• สร้างตารางขนาดหนึ่งตาราง (n + 1) x (m + 1)
• สำหรับ i :=1 ถึง m
  • dp[0, i] :=dp[0, i - 1] + s2[i]
• สำหรับ i :=1 ถึง n
  • dp[i, 0] :=dp[i – 1, 0] + s1[i]
• สำหรับฉันอยู่ในช่วง 1 ถึง n
  • สำหรับ j ในช่วง 1 ถึง m
    • ถ้า s1[i] =s2[j]
      • dp[i, j] :=dp[i – 1, j - 1]
    • อย่างอื่น dp[i, j] =ขั้นต่ำของ dp[i – 1, j] + 1 และ dp[i, j - 1] + 1
• ส่งคืน dp[n, m]

ตัวอย่าง(C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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"));
}

อินพุต

"sea"
"eat"

ผลลัพธ์

231