LeetCode 471. 编码最短长度的字符串

2025-04-06 HGNULB 约 7 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 471. 编码最短长度的字符串

题意分析

题目目标：给定一个字符串，用形如 k[encoded_string] 的规则把它压缩，其中 encoded_string 内部还可以继续包含压缩片段，要求输出长度最短的编码结果；如果压缩之后并不比原串短，就直接返回原串。
核心约束：编码规则是递归定义的——一个片段内部可以嵌套另一个片段，这直接决定了解法必须能表达「先把子问题解到最优，再用最优子结果拼装」。第二个约束是答案的度量是长度而非结构，所以任意两个等长的合法编码都可以，这让我们在转移中只需比较长度。第三个关键信号是数据范围：字符串长度不超过 150，$O(n^3)$ 约三百万次操作绰绰有余，这正是区间动态规划的舒适区。另外要注意包裹一次至少要付出 k[] 三个字符的代价，所以太短的片段压缩必亏。
边界处理：长度不超过 4 的片段永远不可能通过压缩变短（最好的情形 "aaaa" 压成 "4[a]" 也只是等长），可以直接跳过压缩尝试；重复次数可能是两位数甚至三位数，计算代价时不能假设数字只占一个字符；一个片段可能整体就是某个更短单元的整数次重复，也可能只是部分重复，后者不能压；最外层返回的必须是完整区间的最优解，而不是某次局部比较的中间值。

解法：区间动态规划

核心思路

定义 dp[i][j] 为子串 s[i..j] 的最短合法编码字符串。存具体字符串而不只存长度，是因为上层状态需要拼接子结果。

按区间长度递增计算，每个状态考虑三种最外层结构：

不编码，直接保留原子串；

在任意 split 处分成两段，拼接两段的最优编码；

若整个区间由更短单元重复得到，构造 次数[单元的最优编码]。

第三种必须使用单元对应的 dp，而不是原始单元文本，这样才能保留嵌套压缩。区间的最小重复单元用 KMP 前缀函数求得：候选周期为 period = length - prefix[length-1]，只有 length % period == 0 才是完整重复。

正确性用区间长度归纳。最优编码若最外层是并列片段，必被某个分割点覆盖；若最外层是 k[...]，必被整体重复转移覆盖；若两者都不是，只能保留原文。所有引用的子区间都更短且已最优，因此取最短候选得到当前区间最优解。

解题步骤

创建 n * n 的字符串 DP 表，按区间长度从 1 到 n 枚举。

每个状态先初始化为对应原始子串。

枚举全部分割点，用左右最优编码的拼接更新答案。

计算当前区间最小周期；若为完整重复，用重复次数和周期单元的最优编码构造候选。

仅当候选严格更短时替换，最后返回 dp[0][n-1]。

"aaaaa" 可编码为 "5[a]"；"aaaa" 编成 "4[a]" 并未变短，因此仍保留原文。

若可压缩单元再次重复，例如 "aaaaaaaaaabaaaaaaaaaab"，外层候选应使用已优化单元 "10[a]b"，形成 "2[10[a]b]"。

代码实现

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^3)$。

空间复杂度：$O(n^3)$，共有 $O(n^2)$ 个状态，每个状态可能保存 $O(n)$ 长的字符串。

关键点总结

dp[i][j] 必须存具体最优字符串，才能构造上层编码。

分割转移覆盖并列编码块，周期转移覆盖最外层重复结构。

周期内部使用已经优化的 dp，支持嵌套编码。

KMP 候选周期必须通过整除检查，才能确认完整重复。

只在严格更短时替换，避免无收益的等长编码。

易错点总结

周期候选不检查整除，"abcabca" 会被错误当成 "abc" 的完整重复。

方括号内使用原始周期文本，会丢失周期本身可继续压缩的机会。

不枚举分割点会漏掉由多个不同压缩块拼接成的最优答案。

不按区间长度递增计算，会读取尚未完成的子状态。

重复次数可能有多位，必须构造候选字符串后比较真实长度。

未用原子串初始化状态，会让不可压缩区间没有合法答案。

相似题目

题目	难度	考察点
394. 字符串解码	中等	本题的逆过程，用栈把嵌套的 `k[...]` 展开，可用来校验编码结果的正确性
312. 戳气球	困难	区间动态规划的经典代表，难点在于把枚举对象从「先戳谁」换成「最后戳谁」
132. 分割回文串 II	困难	同为「区间内先判性质再分割」的结构，先预处理回文表再做线性动态规划
516. 最长回文子序列	中等	标准的区间动态规划入门题，用来熟悉按长度递增的遍历骨架
459. 重复的子字符串	简单	单独考察本题用到的最小周期判定，前缀函数加整除条件即可
87. 扰乱字符串	困难	同样按分割点递归并依赖记忆化，训练「枚举最外层结构」的思维方式