用C ++编码最短长度的字符串
假设我们有一个非空字符串；我们必须对该字符串进行编码，以使其编码长度最小。
编码规则类似于−k[encoded_string]，其中[]内的encode_string被精确重复k次。我们必须记住，k将是一个正整数，并且编码的字符串将不会为空或有多余的空间。我们可以假设输入字符串仅包含小写字母。如果编码过程没有使字符串变短，则不要对该字符串进行编码。
因此，如果输入类似于“aaaaa”，则输出将为“5[a]”，因为“5[a]”比“aaaaa”短1字符。
为了解决这个问题，我们将遵循以下步骤-
定义一个2D数组dp
定义一个函数collapse()，它将取s，i，j，
temp：=s的子串从索引（i到j-i）
x：=temp与temp连接
pos=x中温度的位置
如果pos>=temp的大小，则-
返回温度
以字符串形式返回（temp/pos的大小），然后连接'['并连接dp[i，i+pos-1]并连接']'
定义一个函数encode()，需要s，
n：=s的大小
dp：=定义一个大小为nxn的2D数组
对于初始化l：=1，当l<=n时，更新（将l增加1），-
dp[i，j]：=s的子串，从索引i到j-i
对于初始化k：=i，当k<j时，更新（将k增加1），-
rep：=崩溃(s,i,j)
如果rep的大小<=dp[i，j]的大小，则-
dp[i，j]：=温度
temp：=dp[i，k]+dp[k+1，j]
如果temp的大小<dp[i，j]的大小，则-
dp[i，j]：=rep
对于初始化i：=0，j：=l-1，当j<n时，更新（i增加1），（j增加1），-
返回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]"