LeetCode 471. 编码最短长度的字符串
题目描述
题意分析
将非空字符串写成尽可能短的等价编码。连续重复的片段可以写成
k[encoded_string]，括号内也允许继续编码；若编码不能缩短长度，就保留原文。多个答案同样短时，返回任意一个。
解法：区间动态规划 + 最短整周期
核心思路
[!blue]
一段字符串既可能整体重复，也可能由几个不同的可压缩片段拼接而成，不能只压缩整串。定义
dp[i][j]为子串s[i..j]的最短编码，保存字符串本身，更新时比较编码后的长度。按区间长度递增计算，让更短片段的答案先准备好。先用原文初始化状态。再枚举每个分割点
split，比较dp[i][split] + dp[split + 1][j]。如果最优表示由多个部分拼接，总能在其中一个部分的边界切开；左右分别取最短编码，不会比使用其他编码更长，因此两段转移也能覆盖更多段的拼接。还要尝试整段折叠。设当前长度为
length，最短整周期为period，若period < length，当前串就是首个周期片段重复length / period次，可构造重复次数[dp[i][i + period - 1]]。括号内使用周期片段已经求出的最短编码，才能支持嵌套压缩；整段折叠仍要与原文、分段方案比较，不能一发现重复就强制采用。
minPeriod使用 KMP 前缀函数。prefix[t]表示当前区间前t + 1个字符的最长相等真前后缀长度，真前后缀不能是整个字符串。已匹配长度为matched时，如果新字符不能接上，就退到prefix[matched - 1]，尝试之前匹配部分的更短相等前后缀；能够接上时，匹配长度加一。令
border = prefix[length - 1]，前后缀相等表示将串平移length - border后，重叠部分完全相同，所以得到最短周期候选period = length - border。还必须满足length % period == 0，才能由完整的周期块拼满整段；否则按无整周期处理，返回length。所有候选都只在严格更短时替换当前状态，因此不会为了括号形式而让结果变长；最后返回整个区间的编码。
解题步骤
- 创建二维编码表
dp，依次处理长度1..n的所有区间。- 将
dp[i][j]初始化为原子串，枚举i <= split < j，尝试拼接左右最短编码。- 为当前区间计算前缀函数，取得最短整周期
period。- 若整段包含至少两个完整周期，构造重复形式，与当前最短编码比较。
- 返回
dp[0][n - 1]。
代码实现
class Solution {
public String encode(String s) {
int n = s.length();
String[][] dp = new String[n][n];
// 短区间先完成，分段和周期内部编码都能直接复用。
for (int length = 1; length <= n; length++) {
for (int i = 0; i + length <= n; i++) {
int j = i + length - 1;
dp[i][j] = s.substring(i, j + 1);
for (int split = i; split < j; split++) {
String candidate = dp[i][split] + dp[split + 1][j];
if (candidate.length() < dp[i][j].length()) {
dp[i][j] = candidate;
}
}
int period = minPeriod(s, i, length);
if (period < length) {
// 重复单元使用已经算出的最短编码，允许内部继续压缩。
String candidate = (length / period) + "[" + dp[i][i + period - 1] + "]";
if (candidate.length() < dp[i][j].length()) {
dp[i][j] = candidate;
}
}
}
}
return dp[0][n - 1];
}
private int minPeriod(String s, int start, int length) {
int[] prefix = new int[length];
for (int i = 1; i < length; i++) {
int matched = prefix[i - 1];
while (matched > 0 && s.charAt(start + i) != s.charAt(start + matched)) {
matched = prefix[matched - 1];
}
if (s.charAt(start + i) == s.charAt(start + matched)) {
matched++;
}
prefix[i] = matched;
}
// 最长相等前后缀给出周期候选，还需检查是否整除区间长度。
int period = length - prefix[length - 1];
return length % period == 0 ? period : length;
}
}
import "fmt"
func encode(s string) string {
n := len(s)
dp := make([][]string, n)
for i := range dp {
dp[i] = make([]string, n)
}
// 短区间先完成，分段和周期内部编码都能直接复用。
for length := 1; length <= n; length++ {
for i := 0; i+length <= n; i++ {
j := i + length - 1
dp[i][j] = s[i : j+1]
for split := i; split < j; split++ {
candidate := dp[i][split] + dp[split+1][j]
if len(candidate) < len(dp[i][j]) {
dp[i][j] = candidate
}
}
period := minPeriod(s, i, length)
if period < length {
// 重复单元使用已经算出的最短编码，允许内部继续压缩。
candidate := fmt.Sprintf("%d[%s]", length/period, dp[i][i+period-1])
if len(candidate) < len(dp[i][j]) {
dp[i][j] = candidate
}
}
}
}
return dp[0][n-1]
}
func minPeriod(s string, start int, length int) int {
prefix := make([]int, length)
for i := 1; i < length; i++ {
matched := prefix[i-1]
for matched > 0 && s[start+i] != s[start+matched] {
matched = prefix[matched-1]
}
if s[start+i] == s[start+matched] {
matched++
}
prefix[i] = matched
}
// 最长相等前后缀给出周期候选，还需检查是否整除区间长度。
period := length - prefix[length-1]
if length%period == 0 {
return period
}
return length
}
复杂度分析
- 时间复杂度：$O(n^4)$ 上界。共有 $O(n^2)$ 个区间，每个区间枚举 $O(n)$ 个分割点，每次拼接最多复制 $O(n)$ 个字符；所有区间的前缀函数计算另需 $O(n^3)$。
- 空间复杂度：$O(n^3)$ 存储上界。二维表有 $O(n^2)$ 个编码，每个长度至多为原区间长度 $O(n)$；单次前缀函数还需 $O(n)$ 临时空间。
关键点总结
[!green]
- 状态保存编码字符串，比较其长度决定是否更新。
- 周期候选必须整除区间长度。
- 先算短区间，才能在拼接与折叠时复用已完成的最优编码。
易错点总结
[!yellow]
- 只看相等前后缀就判定重复：长度不能整除时，不构成完整周期。
- 括号内总放原始片段：错过片段内部的进一步压缩。
- 只比较重复形式，不枚举分割点：不能处理由不同片段组成的更短编码。
- 一旦有重复就强制编码：括号和次数本身也占长度。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 459. 重复的子字符串 | 简单 | 判断子串是否由某周期重复组成，是本题选择k[pattern]编码的前置条件。 |