数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律用 C++ 编码字符串以获得最短长度
假设我们有一个非空字符串；我们需要对该字符串进行编码，使其编码后的长度最小。
编码规则如下：k[encoded_string]，其中 [ ] 内的 encoded_string 被精确重复 k 次。我们必须记住，k 将是一个正整数，并且编码后的字符串将不为空或包含额外的空格。我们可以假设输入字符串仅包含小写字母。如果编码过程没有使字符串变短，则不要对该字符串进行编码。
因此，如果输入类似于“aaaaa”，则输出将为“5[a]”，因为“5[a]”比“aaaaa”短 1 个字符。
为了解决这个问题，我们将遵循以下步骤：
定义一个二维数组 dp
定义一个函数 collapse()，它将接收 s、i、j，
temp := 从索引 (i 到 j - i) 的 s 的子字符串
x := temp 与 temp 的连接
pos = temp 在 x 中的位置
如果 pos >= temp 的大小，则：
返回 temp
返回 (temp 的大小 / pos) 作为字符串，然后连接 '[' 连接 dp[i,i+pos-1] 连接 ']'
定义一个函数 encode()，它将接收 s，
n := s 的大小
dp := 定义一个大小为 n x n 的二维数组
用于初始化 l := 1，当 l <= n 时，更新（将 l 增加 1），执行：
用于初始化 i := 0，j := l - 1，当 j < n 时，更新（将 i 增加 1），（将 j 增加 1），执行：
dp[i, j] := 从索引 i 到 j - i 的 s 的子字符串
用于初始化 k := i，当 k < j 时，更新（将 k 增加 1），执行：
temp := dp[i, k] + dp[k + 1, j]
如果 temp 的大小 < dp[i, j] 的大小，则：
dp[i, j] := temp
rep := collapse(s, i, j)
如果 rep 的大小 <= dp[i, j] 的大小，则：
dp[i, j] := rep
返回 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]"
593 次浏览
