原文链接: https://leetcode-cn.com/problems/string-compression-ii
英文原文
Run-length encoding is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string "aabccc" we replace "aa" by "a2" and replace "ccc" by "c3". Thus the compressed string becomes "a2bc3".
Notice that in this problem, we are not adding '1' after single characters.
Given a string s and an integer k. You need to delete at most k characters from s such that the run-length encoded version of s has minimum length.
Find the minimum length of the run-length encoded version of s after deleting at most k characters.
Example 1:
Input: s = "aaabcccd", k = 2 Output: 4 Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.
Example 2:
Input: s = "aabbaa", k = 2 Output: 2 Explanation: If we delete both 'b' characters, the resulting compressed string would be "a4" of length 2.
Example 3:
Input: s = "aaaaaaaaaaa", k = 0 Output: 3 Explanation: Since k is zero, we cannot delete anything. The compressed string is "a11" of length 3.
Constraints:
1 <= s.length <= 1000 <= k <= s.lengthscontains only lowercase English letters.
中文题目
行程长度编码 是一种常用的字符串压缩方法，它将连续的相同字符（重复 2 次或更多次）替换为字符和表示字符计数的数字（行程长度）。例如，用此方法压缩字符串 "aabccc" ，将 "aa" 替换为 "a2" ，"ccc" 替换为` "c3" 。因此压缩后的字符串变为 "a2bc3" 。
注意，本问题中，压缩时没有在单个字符后附加计数 '1' 。
给你一个字符串 s 和一个整数 k 。你需要从字符串 s 中删除最多 k 个字符，以使 s 的行程长度编码长度最小。
请你返回删除最多 k 个字符后，s 行程长度编码的最小长度 。
示例 1：
输入：s = "aaabcccd", k = 2 输出：4 解释：在不删除任何内容的情况下，压缩后的字符串是 "a3bc3d" ，长度为 6 。最优的方案是删除 'b' 和 'd'，这样一来，压缩后的字符串为 "a3c3" ，长度是 4 。
示例 2：
输入：s = "aabbaa", k = 2 输出：2 解释：如果删去两个 'b' 字符，那么压缩后的字符串是长度为 2 的 "a4" 。
示例 3：
输入：s = "aaaaaaaaaaa", k = 0 输出：3 解释：由于 k 等于 0 ，不能删去任何字符。压缩后的字符串是 "a11" ，长度为 3 。
提示：
1 <= s.length <= 1000 <= k <= s.lengths仅包含小写英文字母
通过代码
高赞题解
解题思路
1. 状态的定义
首先将题意转换成 从字符串中，选取 $T = n-k$ 字符，使编码长度最小.
定义 $\text{dp}[p][cnt]$:
- $p$ - 从字符串的第 $p$ 位开始.
- $cnt$ - 当前已经选取了 $cnt$ 个字符.
2. 状态的转移
我们可以从当前的位置 $p$ 开始向后遍历，只要发现后面有字符和 $s[p]$ 相等，则选取。这样我们可以枚举选取的字符数量，进行状态转移。
比如，字符串 $s = ‘aabaaca’, p = 0$。则我们可以从位置 $0$ 开始，选择 $1$ 个 $a$（$\underline{a}abaaca$）, $2$ 个 $a$（$\underline{aa}baaca$）, ……, 直到 $5$ 个 $a$（$\underline{aa}b\underline{aa}c\underline{a}$），然后再在之后的字符串中选取字符。
形式化的转移方程为：
$$ \text{dp}[p][cnt] = \min_{p \leq j < n}(\text{calc}(same) + \text{dp}[j+1][cnt+same]).$$
式中，
$same$ - 字符串的字串 $s[p:j]$ 中和 $s[p]$ 相等的字符数量。
$\text{calc}(x)$ - 长度为 $x$ 的连续字符的编码长度。我们还可以 丢弃 这个字符。
$$ \text{dp}[p][cnt] = \min(\text{dp}[p][cnt], \text{dp}[p+1][cnt]). $$
3. 初始条件
$$ \text{dp}[n][T] = 0 $$
4. 正确性证明
我们注意到，任何选取方案都可以等同于 在字符串中选取了数段 关于某字符连续 的字符。
下面解释 关于某字符连续 的意思：
比如字符串 $\text{aaacbcdcdcdekefe}$：我们选取了其中的
$$\text{\underline{a}a\underline{a}cb\underline{c}dcd\underline{c}d\underline{e}kef\underline{e}}$$
则等同于选择了
$$\text{\underline{aa}a\underline{c}b\underline{c}dcdcd\underline{e}k\underline{e}fe}$$
这里，虽然两个 $\text{c}$ 不连续，但它们关于字符 $\text{c}$ 连续。字符 $\text{e}$ 同理。
[]class Solution { public: int calc(int x) { return (x <= 1)? x : ((x <= 9)? 2 : ((x <= 99)? 3 : 4)); } int getLengthOfOptimalCompression(string s, int k) { int T = s.size() - k; vector<vector<int>> dp(s.size() + 1, vector<int>(T + 1, 100000)); dp[s.size()][T] = 0; // 初始条件 for(int p = s.size() - 1; p >= 0; --p) { for(int cnt = 0; cnt <= T; ++cnt) { // 1. 从此开始选择连续的字符 for(int j = p, same = 0; j < s.size(); ++j) { same += (s[j] == s[p]); if(same + cnt > T) break; dp[p][cnt] = min(dp[p][cnt], calc(same) + dp[j+1][cnt + same]); } // 2. 跳过该字符 dp[p][cnt] = min(dp[p][cnt], dp[p+1][cnt]); } } return dp[0][0]; } };
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 2055 | 5963 | 34.5% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
