เข้ารหัสสตริงที่มีความยาวสั้นที่สุดใน C++

สมมติว่าเรามีสตริงที่ไม่ว่าง เราต้องเข้ารหัสสตริงนี้เพื่อให้มีความยาวน้อยที่สุด

กฎการเข้ารหัสเป็นเหมือน − k[encoded_string] โดยที่ encoded_string ภายใน [ ] จะถูกทำซ้ำ k ครั้งพอดี เราต้องจำไว้ว่า k จะเป็นจำนวนเต็มบวกและสตริงที่เข้ารหัสจะไม่ว่างเปล่าหรือมีพื้นที่เพิ่มเติม เราสามารถสรุปได้ว่าสตริงอินพุตมีเฉพาะตัวพิมพ์เล็กเท่านั้น หากขั้นตอนการเข้ารหัสไม่ได้ทำให้สตริงสั้นลง ก็อย่าเข้ารหัสสตริงนั้น

ดังนั้น หากอินพุตเป็น "aaaaa" เอาต์พุตจะเป็น "5[a]" เนื่องจาก "5[a]" สั้นกว่า "aaaaa" 1 อักขระ

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

• กำหนดอาร์เรย์ 2 มิติหนึ่ง dp

• กำหนดฟังก์ชั่นการยุบ () ซึ่งจะใช้เวลา s, i, j,

• temp :=สตริงย่อยของ s จากดัชนี (i ถึง j - i)

• x :=temp เชื่อมกับ temp

• pos =ตำแหน่งของอุณหภูมิใน x

• ถ้า pos>=ขนาดของ temp แล้ว −

  • อุณหภูมิกลับ

• ส่งคืน (ขนาดของ temp / pos) เป็นสตริง จากนั้นต่อ '[' concatenate dp[i,i+pos-1]concatenate ']'

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

• n :=ขนาดของ s

• dp :=กำหนดอาร์เรย์ 2 มิติขนาด n x n

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

  • สำหรับการเริ่มต้น i :=0, j :=l - 1, เมื่อ j

    • dp[i, j] :=สตริงย่อยของ s จากดัชนี i ถึง j - i

    • สำหรับการเริ่มต้น k :=i เมื่อ k

      • อุณหภูมิ :=dp[i, k] + dp[k + 1, j]

      • ถ้าขนาดของอุณหภูมิ <ขนาดของ dp[i, j] แล้ว −

        • dp[i, j] :=อุณหภูมิ

    • ตัวแทน :=ยุบ (s, i, j)

    • ถ้าขนาดของตัวแทน <=ขนาดของ dp[i, j] แล้ว −

      • dp[i, j] :=ตัวแทน

• กลับ dp[0, n - 1]

ตัวอย่าง

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   vector<vector<string>> dp;
   string collapse(string &s, int i, int j) {
      string temp = s.substr(i, j - i + 1);
      string x = temp + temp;
      auto pos = x.find(temp, 1);
      if (pos >= temp.size())
         return temp;
      return to_string((temp.size() / pos)) + "[" + dp[i][i + pos - 1] + "]";
   }
   string encode(string s) {
      int n = s.size();
      dp = vector<vector<string>>(n, vector<string>(n, ""));
      for (int l = 1; l <= n; l++) {
         for (int i = 0, j = l - 1; j < n; i++, j++) {
            dp[i][j] = s.substr(i, j - i + 1);
            for (int k = i; k < j; k++) {
               string temp = dp[i][k] + dp[k + 1][j];
               if (temp.size() < dp[i][j].size()) {
                  dp[i][j] = temp;
               }
            }
            string rep = collapse(s, i, j);
            if (rep.size() <= dp[i][j].size()) {
               dp[i][j] = rep;
            }
         }
      }
      return dp[0][n - 1];
   }
};
main() {
   Solution ob;
   cout << (ob.encode("bbbbbbbbbb"));
}

อินพุต

"bbbbbbbbbb"

ผลลัพธ์

"10[b]"