โปรแกรมรับการดำเนินการเพื่อแปลงสตริงหนึ่งเป็นสตริงอื่นใน C++

สมมติว่าเรามีสตริง S และ T สองสตริง เราต้องหาลำดับการดำเนินการที่สั้นที่สุดที่เปลี่ยนจาก S เป็น T โดยพื้นฐานแล้วการดำเนินการจะเป็นการลบหรือแทรกอักขระ

ดังนั้น หากอินพุตเป็น S ="xxxy" T ="xxyy" ผลลัพธ์จะเป็น ["x", "x", "-x", "y", "+y"] หมายถึงสถานที่ x สองตัวแรก จากนั้นลบ x ตัวที่ 3 แล้ววาง y แล้วเพิ่ม y ใหม่

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

• สร้างตาราง dp ขนาด 505 x 505
• กำหนดฟังก์ชัน help() ซึ่งจะใช้เวลา i, j, S, T,
• ถ้าฉันมีขนาดเท่ากับ S และ j เท่ากับขนาด T แล้ว −
  • ผลตอบแทน dp[i, j] =0
• ถ้าฉันมีขนาดเท่ากับ S แล้ว −
  • ส่งคืน dp[i, j] =1 + help(i, j + 1, S, T)
• ถ้า j เท่ากับขนาด T แล้ว −
  • ส่งคืน dp[i, j] =1 + help(i + 1, j, S, T)
• ถ้า dp[i, j] ไม่เท่ากับ -1 แล้ว −
  • ส่งคืน dp[i, j]
• อย่าทำ :=1e5, del :=0, ใส่ :=0
• ถ้า S[i] เหมือนกับ T[j] แล้ว −
  • อย่าทำ :=ช่วย (i + 1, j + 1, S, T)
• del :=1 + help(i + 1, j, S, T)
• insert :=1 + help(i, j + 1, S, T)
• minVal :=min({dontDo, del, insert})
• ส่งคืน dp[i, j] =minVal
• กำหนดฟังก์ชัน getPath() ซึ่งจะใช้ i, j, S, T, curr, อาร์เรย์ ret,
• ถ้า curr เท่ากับ 0 และฉันเท่ากับขนาด S และ j เท่ากับขนาด T ดังนั้น −
  • คืนสินค้า
• ถ้า i <ขนาดของ S และ j <ขนาดของ T และ S[i] เท่ากับ T[j] และ dp[i + 1, j + 1] เท่ากับเคอร์ร์ ดังนั้น −
  • ใส่ string(1, S[i]) ที่ส่วนท้ายของ ret
  • getPath(i + 1, j+1, S, T, curr, ret)
• มิฉะนั้น เมื่อ dp[i + 1, j] + 1 เหมือนกับ curr แล้ว −
  • แทรก ("-" concatenate string(1, S[i])) ที่ส่วนท้ายของ ret
  • getPath(i + 1, j, S, T, curr - 1, ย้อนกลับ)
• มิฉะนั้น
  • แทรก ("+" concatenate string(1, T[j])) ที่ส่วนท้ายของ ret
  • getPath(i, j + 1, S, T, curr - 1, ย้อนกลับ)
• จากวิธีหลัก ให้ทำดังนี้ -
• เติม dp ด้วย -1
• กำหนดอาร์เรย์ ret
• x :=ช่วย(0, 0, S, T)
• getPath(0, 0, S, T, x, ย้อน)
• คืนสินค้า

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

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v) {
   cout << "[";
   for (int i = 0; i < v.size(); i++) {
      cout << v[i] << ", ";
   }
   cout << "]" << endl;
}
int dp[505][505];
class Solution {
   public:
   int help(int i, int j, string& S, string& T) {
      if (i == S.size() && j == T.size())
         return dp[i][j] = 0;
      if (i == S.size())
         return dp[i][j] = 1 + help(i, j + 1, S, T);
      if (j == T.size())
         return dp[i][j] = 1 + help(i + 1, j, S, T);
      if (dp[i][j] != -1)
         return dp[i][j];
      int dontDo = 1e5;
      int del = 0;
      int insert = 0;
      if (S[i] == T[j])
         dontDo = help(i + 1, j + 1, S, T);
      del = 1 + help(i + 1, j, S, T);
      insert = 1 + help(i, j + 1, S, T);
      int minVal = min({dontDo, del, insert});
      return dp[i][j] = minVal;
   }
   void getPath(int i, int j, string& S, string& T, int curr, vector<string>& ret) {
      if (curr == 0 && i == S.size() && j == T.size())
         return;
      if (i < S.size() && j < T.size() && S[i] == T[j] && dp[i + 1][j + 1] == curr) {
         ret.push_back(string(1, S[i]));
         getPath(i + 1, j + 1, S, T, curr, ret);
      }else if (dp[i + 1][j] + 1 == curr) {
         ret.push_back("-" + string(1, S[i]));
         getPath(i + 1, j, S, T, curr - 1, ret);
      }else {
         ret.push_back("+" + string(1, T[j]));
         getPath(i, j + 1, S, T, curr - 1, ret);
      }
   }  
   vector<string> solve(string S, string T) {
      memset(dp, -1, sizeof dp);
      vector<string> ret;
      int x = help(0, 0, S, T);
      getPath(0, 0, S, T, x, ret);
      return ret;
   }
};
vector<string> solve(string source, string target) {
   return (new Solution())->solve(source, target);
}
main(){
   string S = "xxxy", T = "xxyy";
   print_vector(solve(S, T));
}

อินพุต

"xxxy", "xxyy"

ผลลัพธ์

[x, x, -x, y, +y, ]