Mã hóa chuỗi có độ dài ngắn nhất trong C ++

Giả sử chúng ta có một chuỗi không rỗng; chúng ta phải mã hóa chuỗi này sao cho độ dài được mã hóa của nó sẽ là tối thiểu.

Quy tắc mã hóa giống như - k [chuỗi mã hóa], trong đó chuỗi mã hóa bên trong [] được lặp lại chính xác k lần. Chúng ta phải nhớ rằng k sẽ là một số nguyên dương và chuỗi được mã hóa sẽ không bị trống hoặc có thêm khoảng trắng. Chúng ta có thể giả định rằng chuỗi đầu vào chỉ chứa các chữ cái thường. Nếu quá trình mã hóa không làm cho chuỗi ngắn hơn, thì không mã hóa chuỗi đó.

Vì vậy, nếu đầu vào là "aaaaa", thì đầu ra sẽ là "5 [a]" vì "5 [a]" ngắn hơn "aaaaa" 1 ký tự.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một dp mảng 2D

• Xác định một hàm sụp đổ (), điều này sẽ lấy s, i, j,

• temp:=chuỗi con của s từ chỉ mục (i đến j - i)

• x:=ghép tạm thời với tạm thời

• pos =vị trí của nhiệt độ trong x

• if pos> =size of temp, then -

  • trở lại nhiệt độ

• return (kích thước của temp / pos) dưới dạng chuỗi rồi nối '[' concatenate dp [i, i + pos-1] concatenate ']'

• Xác định một mã hóa hàm (), điều này sẽ mất s,

• n:=kích thước của s

• dp:=Xác định một mảng 2D có kích thước n x n

• để khởi tạo l:=1, khi l <=n, cập nhật (tăng l lên 1), thực hiện -

  • để khởi tạo i:=0, j:=l - 1, khi j

    • dp [i, j]:=chuỗi con của s từ chỉ mục i đến j - i

    • để khởi tạo k:=i, khi k

      • tạm thời:=dp [i, k] + dp [k + 1, j]

      • nếu kích thước của temp

        • dp [i, j]:=temp

    • đại diện:=sụp đổ (s, i, j)

    • nếu kích thước của đại diện <=kích thước của dp [i, j], thì -

      • dp [i, j]:=rep

• trả về dp [0, n - 1]

Ví dụ

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

Đầu vào

"bbbbbbbbbb"

Đầu ra

"10[b]"