0471：编码最短长度的字符串（★★）

力扣第 471 题

题目

给定一个 非空 字符串，将其编码为具有最短长度的字符串。

编码规则是：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 <= 150
• s 由小写英文字母组成

分析

典型的区间 dp，令 dp[i][j] 代表 s[i:j+1] 的最短编码，有三种情况：

• s[i:j+1] 不变
• dp[i][k] +dp[k+1][j]
• 表示为 k[子串]

表示为 k[子串] 类似问题 0459，可以用 (ss+ss).find(ss,1) 来查找。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def encode(self, s: str) -> str:
	n = len(s)
	dp = [['']*n for _ in range(n)]
	for i in range(n-1, -1, -1):
		for j in range(i, n):
			dp[i][j] = ss = s[i:j+1]
			x = (ss+ss).find(ss, 1)
			dp[i][j] = min(dp[i][j], str(len(ss)//x)+'['+dp[i][i+x-1]+']', key=len)
			for k in range(i+1, j):
				dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j], key=len)
	return dp[0][-1]

304 ms