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

Cho chuỗi không rỗng, hãy mã hóa chuỗi sao cho độ dài mã hóa nhỏ nhất. Quy tắc mã hóa: k[encoded_string], trong đó encoded_string bên trong [] lặp lại chính xác k lần. k là số nguyên dương, encoded_string không rỗng. Chuỗi chỉ chứa chữ cái thường. Nếu mã hóa không làm ngắn hơn chuỗi gốc thì không mã hóa.

Ví dụ: "aaaaa" → "5[a]" (ngắn hơn 1 ký tự).

Phương pháp giải

Sử dụng quy hoạch động 2D dp[i][j] lưu chuỗi mã hóa tối ưu cho chuỗi con từ i đến j. Hàm collapse() tìm chuỗi lặp lại. Duyệt độ dàisubstring từ 1 đến n, thử chia tại mọi vị trí k và áp dụng collapse.

Ví dụ chương trình

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector> 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>(n, vector(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];
    }
};

int main() {
    Solution ob;
    cout << ob.encode("bbbbbbbbbb");
    return 0;
}

Đầu vào

"bbbbbbbbbb"

Đầu ra

"10[b]"