ซูเปอร์ซีเควนซ์ร่วมที่สั้นที่สุดใน C++

สมมติว่าเรามีสตริง str1 และ str2 สองสตริง เราต้องหาสตริงที่สั้นที่สุดที่มีทั้ง str1 และ str2 เป็นลำดับรอง อาจมีมากกว่าหนึ่งผลลัพธ์ ดังนั้นเราจะส่งคืนผลลัพธ์เพียงรายการเดียวเท่านั้น

ดังที่คุณทราบสตริง S ถูกเรียกว่าเป็นผลสืบเนื่องของสตริง T หากการลบอักขระบางตัวออกจาก T (อาจเป็น 0 และเลือกอักขระที่ใดก็ได้จาก T) ผลลัพธ์ในสตริง S

ดังนั้น หากอินพุตเป็นเหมือน "acab", "bac" ผลลัพธ์จะเป็น "bacab" นั่นเป็นเพราะว่าสองสตริงที่ให้มานั้นเป็นส่วนรองของสิ่งนี้

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

• กำหนดฟังก์ชัน getLCS() ซึ่งจะใช้เวลา s1, s2

• ret :=สตริงว่าง

• n :=ขนาดของ s1, m :=ขนาดของ s2

• กำหนดขนาดอาร์เรย์ 2 มิติหนึ่ง dp (n + 1) x (m + 1)

• ผม :=น, เจ :=ม.

• s1 :=เชื่อมสตริงว่างก่อน s1

• s2 :=เชื่อมสตริงว่างก่อน s2

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • สำหรับการเริ่มต้น j :=1 เมื่อ j <=m อัปเดต (เพิ่ม j ขึ้น 1) ทำ −

    • ถ้า s1[i] เหมือนกับ s2[j] แล้ว −

      • dp[i, j] :=1 + dp[i - 1, j - 1]

    • มิฉะนั้น

      • dp[i, j] :=สูงสุดของ dp[i - 1, j] และ dp[i, j - 1]

• ในขณะที่ (i ไม่ใช่ศูนย์และ j ไม่ใช่ศูนย์) ทำ -

  • ถ้า dp[i, j] เหมือนกับ dp[i - 1, j] แล้ว −

    • (ลดลง 1)

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • ถ้า dp[i, j] เหมือนกับ dp[i, j - 1] แล้ว −

    • (ลด j โดย 1)

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • ret :=ret + s1[i]

  • (ลดลง 1)

  • (ลด j โดย 1)

• ย้อนกลับอาร์เรย์ ret

• รีเทิร์น

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• s3 :=getLCS(str1, str2)

• ret :=สตริงว่าง i :=0, j :=0, k :=0

• ในขณะที่ k <ขนาดของ s3 ทำ −

  • ถ้าฉัน <ขนาดของ str1 และ str1[i] ไม่เท่ากับ s3[k] ดังนั้น −

    • ret :=ret + str1[i]

    • (เพิ่ม i ขึ้น 1)

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • ถ้า j <ขนาดของ str2 และ str2[j] ไม่เท่ากับ s3[k] ดังนั้น −

    • ret :=ret + str2[j]

    • (เพิ่มขึ้น j โดย 1)

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • ret :=ret + s3[k]

  • (เพิ่ม i, j, k ขึ้น 1)

• ในขณะที่ฉัน <ขนาดของ str1 ทำ −

  • ret :=ret + str1[i]

  • (เพิ่ม i ขึ้น 1)

• ในขณะที่ j <ขนาดของ str2 ทำ −

  • ret :=ret + str2[j]

  • (เพิ่มขึ้น j โดย 1)

• รีเทิร์น

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string shortestCommonSupersequence(string str1, string str2){
      string s3 = getLCS(str1, str2);
      string ret = "";
      int i = 0;
      int j = 0;
      int k = 0;
      while (k < s3.size()) {
         if (i < str1.size() && str1[i] != s3[k]) {
            ret += str1[i];
            i++;
            continue;
         }
         if (j < str2.size() && str2[j] != s3[k]) {
            ret += str2[j];
            j++;
            continue;
         }
         ret += s3[k];
         k++;
         i++;
         j++;
      }
      while (i < str1.size()) {
         ret += str1[i];
         i++;
      }
      while (j < str2.size()) {
         ret += str2[j];
         j++;
      }
      return ret;
   }
   string getLCS(string s1, string s2){
      string ret = "";
      int n = s1.size();
      int m = s2.size();
      vector<vector<int> > dp(n + 1, vector<int>(m + 1));
      int i = n;
      int j = m;
      s1 = " " + s1;
      s2 = " " + s2;
      for (int i = 1; i <= n; i++) {
         for (int j = 1; j <= m; j++) {
            if (s1[i] == s2[j]) {
               dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
               dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
         }
      }
      while (i && j) {
         if (dp[i][j] == dp[i - 1][j]) {
            i--;
            continue;
         }
         if (dp[i][j] == dp[i][j - 1]) {
            j--;
            continue;
         }
         ret += s1[i];
         i--;
         j--;
      }
      reverse(ret.begin(), ret.end());
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.shortestCommonSupersequence("acab", "bac"));
}

อินพุต

"acab", "bac"

ผลลัพธ์

bacab