难度: Hard
Submission
运行时间: 56 ms
内存: 16.8 MB
from functools import lru_cache
# '''
# 递归进行压缩，把s切分成两半，左边一半如果能够按照整倍数压缩，就进行压缩，先把左边一半变成最短的，
# 然后递归处理右边一半，把两半都处理完之后的字符串拼接回来，最短的拼接字符串就是答案，判断能不能进行
# 整倍数压缩的时候，问题转换为找串的重复子串问题
# '''
class Solution:
# 返回最短的以倍数压缩后的字符串，不能压缩返回原字符串
@lru_cache(typed=False)
def compress(self, s: str):
if s == '' or len(s) == 1:
return s
t = s + s
n = len(s)
ans = s
# 找重复子串位置
idx = t.find(s, 1)
if idx == n:
return ans
cnt = len(s) // idx
encode_str = self.encode(s[:idx])
ss = str(cnt) + '[' + encode_str + ']'
if len(ss) < len(ans):
ans = ss
return ans
@lru_cache(typed=False)
def encode(self, s: str) -> str:
#print(s)
if s == '' or len(s) == 1:
return s
ans = s
for i in range(0, len(s)):
ss = self.compress(s[:i+1]) + self.encode(s[i+1:])
if len(ss) < len(ans):
ans = ss
return ans
Explain
这个题解采用递归的方式进行字符串压缩。主要思路是将字符串切分成两半，左边一半如果能够按照整倍数压缩，就进行压缩，得到左边一半的最短压缩形式。然后递归处理右边一半，将两半处理完后的字符串拼接起来，其中最短的拼接字符串就是最终的答案。在判断能否进行整倍数压缩时，问题转化为寻找字符串的重复子串。
时间复杂度: O(n^2)
空间复杂度: O(n)
from functools import lru_cache
class Solution:
@lru_cache(typed=False)
def compress(self, s: str):
# 基础情况：空字符串或长度为1的字符串无法压缩
if s == '' or len(s) == 1:
return s
t = s + s
n = len(s)
ans = s
# 寻找重复子串的位置
idx = t.find(s, 1)
if idx == n:
return ans
# 计算重复子串的个数，并递归压缩重复子串
cnt = len(s) // idx
encode_str = self.encode(s[:idx])
ss = str(cnt) + '[' + encode_str + ']'
if len(ss) < len(ans):
ans = ss
return ans
@lru_cache(typed=False)
def encode(self, s: str) -> str:
# 基础情况：空字符串或长度为1的字符串无法压缩
if s == '' or len(s) == 1:
return s
ans = s
# 枚举切分点，递归处理左右两半部分
for i in range(0, len(s)):
ss = self.compress(s[:i+1]) + self.encode(s[i+1:])
if len(ss) < len(ans):
ans = ss
return ans
Explore
这个算法通过递归方式试图找到每个子字符串的最短压缩形式，并在各个级别上尝试所有可能的切分点，理论上可以找到全局最短的压缩结果。然而，因为算法在每一步选择时只考虑当前切分产生的最短结果而不是整体最短，所以在某些情况下可能只达到局部最优。此外，全局最优解的确保还依赖于递归过程中正确的切割和压缩选择，可能需要额外的优化或者更复杂的动态规划方法来确保最短结果。
题解中的算法采用平分的方法进行说明，这是因为平分是一种简单且常见的递归策略，便于理解和实现。实际上，算法并不限于平分，而是尝试了所有可能的切分点，这包括了不同长度的左右切分。通过枚举所有切分点，算法试图找到任何可能的压缩优势，因此已经考虑了多种分割方式，以寻求最优解。
在寻找重复子串的过程中，算法利用了字符串自身与其自身拼接（s+s）的方法，并寻找第二个字符串开始出现的位置。这个位置（idx）如果小于字符串的长度（n），表示找到了一个重复的单元。该位置表示最小的可重复单元的长度，从而可以对整个字符串进行压缩。通过这种方式，算法确保了找到的重复单元是最小的，从而最大程度地实现压缩。
在处理较长的字符串时，确实可能遇到性能问题，主要是因为递归的深度过深及切分操作过多导致的计算量大增。为了解决这个问题，可以采用多种策略：1. 使用动态规划替代纯递归，存储已经计算过的结果，避免重复计算。2. 限制递归的深度或者在递归过程中加入剪枝，放弃那些明显不会产生最短结果的路径。3. 在实际应用中，可以考虑使用迭代方法代替递归，或者使用尾递归优化，减少内存消耗。