文章目录
- 摘要
- 描述
- 题解答案
- 题解代码分析
- 题解代码分析
- 为什么用区间 DP
- 拆分的意义
- 整体重复的判断逻辑
- 示例测试及结果
- 时间复杂度
- 空间复杂度
- 总结
摘要
LeetCode 471《编码最短长度的字符串》是一道非常典型但也非常容易被低估的动态规划题。
表面上看，它只是把字符串压缩成类似k[substring]的形式；但真正难的地方在于——什么时候该压缩，什么时候不该压缩，以及如何保证整体长度是最短的。
这道题和真实业务里很多“字符串优化”“配置压缩”“协议编码”问题的思路是高度相通的。
本文会从直觉思路开始，逐步推到 DP 解法，并给出一个 Swift 的可运行 Demo。
描述
题目要求我们实现一个函数：
给定一个字符串
s，对其进行编码，使编码后的字符串长度最短。
编码规则是：
- 如果一个字符串可以表示为某个子串重复多次
- 可以写成：
k[encoded_string] - 其中
k是重复次数，encoded_string是被重复的字符串
比如：
"aaaaa"→"5[a]""ababab"→"3[ab]""aabcaabcd"→"2[aabc]d"
但要注意一个非常重要的点：
如果编码后的字符串不比原字符串短，那就不要编码。
这句话，基本就是这道题 80% 的难点来源。
题解答案
这道题的核心思路可以总结为一句话：
用区间 DP，枚举每一个子串的最优编码结果。
我们用一个二维 DP：
dp[i][j] 表示字符串 s[i...j] 的最短编码结果对于任意一个子串，我们有两种选择：
不做压缩，直接用原字符串
尝试压缩
- 要么拆分成两段
- 要么整个子串由某个更小的子串重复构成
最终取长度最短的那个方案。
->String{letchars=Array(s)letn=chars.countifn==0{return""}// dp[i][j] 表示 s[i...j] 的最短编码字符串vardp=Array(repeating:Array(repeating:"",count:n),count:n)// 单个字符初始化foriin0..<n{dp[i][i]=String(chars[i])}// 按区间长度递增forlenin2...n{foriin0...n-len{letj=i+len-1letsubstring=String(chars[i...j])dp[i][j]=substring// 默认不编码// 情况一：拆分forkini..<j{letleft=dp[i][k]letright=dp[k+1][j]ifleft.count+right.count<dp[i][j].count{dp[i][j]=left+right}}// 情况二：整体重复letpattern=findRepeatPattern(substring)ifletp=pattern{lettimes=substring.count/p.countletencoded="\(times)[\(p)]"ifencoded.count<dp[i][j].count{dp[i][j]=encoded}}}}returndp[0][n-1]}// 判断字符串是否由某个子串重复构成privatefuncfindRepeatPattern(_s:String)->String?{letchars=Array(s)letn=chars.countforlenin1...n/2{ifn%len!=0{continue}letpattern=Array(chars[0..<len])varmatch=trueforiinstride(from:0,to:n,by:len){ifArray(chars[i..<i+len])!=pattern{match=falsebreak}}ifmatch{returnString(pattern)}}returnnil}}题解代码分析
这段代码比较长，我们分几块慢慢聊。
为什么用区间 DP
这道题的编码是强子结构问题：
- 子串的最优解，会影响大串的最优解
- 拆分位置不同，结果完全不同
所以：
- 一维 DP 根本不够
- 必须知道每个区间的最优编码
这也是dp[i][j]出现的原因。
拆分的意义
这段代码：
forkini..<j{letleft=dp[i][k]letright=dp[k+1][j]ifleft.count+right.count<dp[i][j].count{dp[i][j]=left+right}}解决的是这种情况：
"aabcaabcd" = "aabc" + "aabcd"有些字符串整体无法压缩，但拆开之后能变短。
这在实际场景中非常常见，比如：
- 模板字符串
- 日志前缀 + 重复内容
- 协议字段拼接
整体重复的判断逻辑
这段是整题最容易写错的地方：
letpattern=findRepeatPattern(substring)它的本质是在问：
这个字符串是不是由一个更短的字符串重复 N 次得到的？
我们做法非常直接：
- 枚举所有可能的子串长度
len - 判断能不能完整覆盖原字符串
- 每一段都严格相等才算成功
注意一个关键点：
即使可以压缩，也要比较长度，不能强行压。
这正是很多人第一次写这道题会踩的坑。
示例测试及结果
我们来跑几个经典用例。
letsolution=Solution()print(solution.encode("aaa"))// 3[a]print(solution.encode("ababab"))// 3[ab]print(solution.encode("aabcaabcd"))// 2[aabc]dprint(solution.encode("abcde"))// abcde输出结果：
3[a] 3[ab] 2[aabc]d abcde可以看到：
- 能压缩的就压
- 压了不划算的，坚决不动
这正是题目想要的效果。
时间复杂度
时间复杂度主要来自三部分：
- 区间 DP：
O(n^2) - 每个区间尝试拆分：
O(n) - 每次判断重复模式：
O(n)
综合下来：
- 时间复杂度是 O(n³)
虽然看起来不低，但题目本身对n的限制并不大，是完全可以接受的。
空间复杂度
- 使用了一个
n x n的 DP 表 - 额外的字符串操作是常数级
所以：
- 空间复杂度是 O(n²)
总结
LeetCode 471 是一道非常适合用来检验你是否真正理解区间 DP 的题。
它至少同时考察了三点能力：
- 能不能正确建模子问题
- 能不能处理“压不压”的决策问题
- 能不能在字符串问题里保持足够的耐心和严谨
