题目描述
给定一个 非空 字符串，将其编码为具有最短长度的字符串。
编码规则是：k[encoded_string]，其中在方括号 encoded_string 中的内容重复 k 次。
注：
- k 为正整数
- 如果编码的过程不能使字符串缩短，则不要对其进行编码。如果有多种编码方式，返回 任意一种 即可
示例 1：
输入：s = "aaa"
输出："aaa"
解释：无法将其编码为更短的字符串，因此不进行编码。
示例 2：
输入：s = "aaaaa"
输出："5[a]"
解释："5[a]" 比 "aaaaa" 短 1 个字符。
示例 3：
输入：s = "aaaaaaaaaa"
输出："10[a]"
解释："a9[a]" 或 "9[a]a" 都是合法的编码，和 "10[a]" 一样长度都为 5。
示例 4：
输入：s = "aabcaabcd"
输出："2[aabc]d"
解释："aabc" 出现两次，因此一种答案可以是 "2[aabc]d"。
示例 5：
输入：s = "abbbabbbcabbbabbbc"
输出："2[2[abbb]c]"
解释："abbbabbbc" 出现两次，但是 "abbbabbbc" 可以编码为 "2[abbb]c"，因此一种答案可以是 "2[2[abbb]c]"。
提示：
1 <= s.length <= 150s 由小写英文字母组成
解法
方法一：动态规划（区间 DP）
在这道题中，我们需要判断一个字符串是否能够进行压缩，也即是说，一个字符串是否能通过其子串重复多次构成。我们可以利用第 $459$ 题的方法来判断，定义一个方法 $g(i, j)$，表示将字符串 $s[i...j]$ 进行压缩后得到的字符串。
接下来，我们用动态规划的方法，将字符串 $s$ 编码成一个最短长度的字符串。
我们定义 $f[i][j]$ 表示将字符串 $s[i..j]$ 编码后的最短字符串。如果直接将 $s[i..j]$ 进行压缩编码，那么 $f[i][j] = g(i, j)$，如果我们将其分成两个子串进行编码，那么 $f[i][j]$ 的值为 $f[i][k] + f[k + 1][j]$ 的最小值，其中 $i \le k < j$。取两种情况下长度较小的字符串即可。
在枚举 $i$ 和 $j$ 时，我们可以从大到小枚举 $i$，然后从小到大枚举 $j$，这样我们在计算 $f[i][j]$ 时，$f[i][k]$ 和 $f[k + 1][j]$ 的值都已经被计算过了。
时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。其中 $n$ 是字符串 $s$ 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution:
def encode(self, s: str) -> str:
def g(i: int, j: int) -> str:
t = s[i : j + 1]
if len(t) < 5:
return t
k = (t + t).index(t, 1)
if k < len(t):
cnt = len(t) // k
return f"{cnt}[{f[i][i + k - 1]}]"
return t
n = len(s)
f = [[None] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
f[i][j] = g(i, j)
if j - i + 1 > 4:
for k in range(i, j):
t = f[i][k] + f[k + 1][j]
if len(f[i][j]) > len(t):
f[i][j] = t
return f[0][-1]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | class Solution {
private String s;
private String[][] f;
public String encode(String s) {
this.s = s;
int n = s.length();
f = new String[n][n];
for (int i = n - 1; i >= 0; --i) {
for (int j = i; j < n; ++j) {
f[i][j] = g(i, j);
if (j - i + 1 > 4) {
for (int k = i; k < j; ++k) {
String t = f[i][k] + f[k + 1][j];
if (f[i][j].length() > t.length()) {
f[i][j] = t;
}
}
}
}
}
return f[0][n - 1];
}
private String g(int i, int j) {
String t = s.substring(i, j + 1);
if (t.length() < 5) {
return t;
}
int k = (t + t).indexOf(t, 1);
if (k < t.length()) {
int cnt = t.length() / k;
return String.format("%d[%s]", cnt, f[i][i + k - 1]);
}
return t;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | class Solution {
public:
string encode(string s) {
int n = s.size();
vector<vector<string>> f(n, vector<string>(n));
auto g = [&](int i, int j) {
string t = s.substr(i, j - i + 1);
if (t.size() < 5) {
return t;
}
int k = (t + t).find(t, 1);
if (k < t.size()) {
int cnt = t.size() / k;
return to_string(cnt) + "[" + f[i][i + k - 1] + "]";
}
return t;
};
for (int i = n - 1; ~i; --i) {
for (int j = i; j < n; ++j) {
f[i][j] = g(i, j);
if (j - i + 1 > 4) {
for (int k = i; k < j; ++k) {
string t = f[i][k] + f[k + 1][j];
if (t.size() < f[i][j].size()) {
f[i][j] = t;
}
}
}
}
}
return f[0][n - 1];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | func encode(s string) string {
n := len(s)
f := make([][]string, n)
for i := range f {
f[i] = make([]string, n)
}
g := func(i, j int) string {
t := s[i : j+1]
if len(t) < 5 {
return t
}
k := strings.Index((t + t)[1:], t) + 1
if k < len(t) {
cnt := len(t) / k
return strconv.Itoa(cnt) + "[" + f[i][i+k-1] + "]"
}
return t
}
for i := n - 1; i >= 0; i-- {
for j := i; j < n; j++ {
f[i][j] = g(i, j)
if j-i+1 > 4 {
for k := i; k < j; k++ {
t := f[i][k] + f[k+1][j]
if len(t) < len(f[i][j]) {
f[i][j] = t
}
}
}
}
}
return f[0][n-1]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | function encode(s: string): string {
const n = s.length;
const f: string[][] = new Array(n).fill(0).map(() => new Array(n).fill(''));
const g = (i: number, j: number): string => {
const t = s.slice(i, j + 1);
if (t.length < 5) {
return t;
}
const k = t.repeat(2).indexOf(t, 1);
if (k < t.length) {
const cnt = Math.floor(t.length / k);
return cnt + '[' + f[i][i + k - 1] + ']';
}
return t;
};
for (let i = n - 1; i >= 0; --i) {
for (let j = i; j < n; ++j) {
f[i][j] = g(i, j);
if (j - i + 1 > 4) {
for (let k = i; k < j; ++k) {
const t = f[i][k] + f[k + 1][j];
if (t.length < f[i][j].length) {
f[i][j] = t;
}
}
}
}
}
return f[0][n - 1];
}
|