深圳台历制作,seo中介平台,网页制作专业信息,wordpress部署到外网本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 行程长度编码 是一种常用的字符串压缩方法它将连续的相同字符重复 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 仅包含小写英文字母 解法 动态规划字符串
称给定字符串 s s s 为「原串」压缩后字符串 t t t 为「压串」。目标是从 s s s 中删除至多 k k k 个字符使其对应的 t t t 长度最小。
压串 t t t 由字母和数字间隔组成 c x c_x cx 表示字母 d x d_x dx 表示次数 ( c x , d x ) (c_x, d_x) (cx,dx) 表示原串 s s s 中连续出现了 d x d_x dx 次字母 c x c_x cx 。当出现次数为 1 1 1 时我们省略 d x d_x dx t c 1 d 1 c 2 d 2 … c m d m t c_1 d_1 c_2 d_2 \dots c_m d_m tc1d1c2d2…cmdm 我们可以根据 t t t 的形式进行动态规划。在状态转移的过程中每一次只处理 t t t 中一个二元组 ( c x , d x ) (c_x, d_x) (cx,dx) 。
我们用 f [ i ] [ j ] f[i][j] f[i][j] 表示对于原串 s s s 的前 i i i 个字符通过删除其中的 j j j 个字符剩余的 i − j i - j i−j 个字符可以得到的最小的压串的长度。为了对边界条件进行处理这里的 i i i 和 j j j 都从 1 1 1 开始编号。 i i i 的最大值为 ∣ s ∣ |s| ∣s∣原串的长度 j j j 的最大值为 k k k 。
动态规划的边界条件为 f [ 0 ] [ 0 ] 0 f[0][0] 0 f[0][0]0 表示空串对应的压串长度为 0 0 0 。由于要求的是 f [ i ] [ j ] f[i][j] f[i][j] 的最小值所以先把它们的值初始化为一个很大的正整数。最终答案即为 f [ n ] [ 0 … k ] f[n][0\dots k] f[n][0…k] 中的最小值即我们可以从 s s s 中删除至多 k k k 个字符。由于删除一个字符得到的压串的长度永远不会劣于保留该字符因此实际上最终的答案就是 f [ n ] [ k ] f[n][k] f[n][k] 即我们恰好删除 k k k 个字符。注意这里的状态表示中我们不关心到底删除了哪 j j j 个字符。
如何进行状态转移呢我们可以考虑是否删除第 i i i 个字符。 如果第 i i i 个字符被删除则前 i − 1 i-1 i−1 个字符中就要删除 j − 1 j-1 j−1 个字符状态转移方程为 f [ i ] [ j ] f [ i − 1 ] [ j − 1 ] f[i][j] f[i - 1][j - 1] f[i][j]f[i−1][j−1] 如果第 i i i 个字符没有被删除那么考虑以该字符 s [ i ] s[i] s[i] 结尾的一个 ( c x , d x ) (c_x, d_x) (cx,dx) 二元组其中 c x s [ i ] c_x s[i] cxs[i] 。我们要在 [ 1 , i ) [1, i) [1,i) 的范围内再选择若干个包括零个与 s [ i ] s[i] s[i] 相同的字符即保留一个、两个…… d x d_x dx 个 c x c_x cx一起进行压缩。在选择范围内与 s [ i ] s[i] s[i] 不同的字符全部被删除。通俗来说如果保留字符 c x c_x cx 则此时往前尽量选择保留与字符 c x c_x cx 相同的字符。这个状态转移确实不好理解但仔细思考一下最优解应该是包含在里面的。 形式化地说我们选择了位置 p 1 p 2 ⋯ p d x − 1 i p_1 p_2 \dots p_{d_x - 1} i p1p2⋯pdx−1i 其中 s [ p 1 ] s [ p 2 ] ⋯ s [ p d x − 1 ] s [ i ] c x s[p_1] s[p_2] \dots s[p_{d_x - 1}] s[i] c_x s[p1]s[p2]⋯s[pdx−1]s[i]cx 那么我们选择的范围为 [ p 1 , i ] [p_1, i] [p1,i] 在其中选择了 d x d_x dx 个字符 c x c_x cx 剩余的 i − p 1 1 − d x i - p_1 1 - d_x i−p11−dx 个字符无论是否为 c x c_x cx都必须被删除。那么前 p 1 − 1 p_1 - 1 p1−1 个字符中就有 j − ( i − p 1 1 − d x ) j - (i - p_1 1 - d_x) j−(i−p11−dx) 个字符被删除状态转移方程为 f [ i ] [ j ] min X d { f [ p 1 − 1 ] [ j − ( i − p 1 1 − d x ) ] c o s t ( d x ) } f[i][j] \min_{ X_d } \{ f[p_1 - 1][j - (i - p_1 1 - d_x)] cost(d_x) \} f[i][j]Xdmin{f[p1−1][j−(i−p11−dx)]cost(dx)} 其中 X d X_d Xd 表示「包含了所有选择 p 1 , … , p d x − 1 p_1, \dots, p_{d_x - 1} p1,…,pdx−1 的方案集合」 c o s t ( d x ) cost(d_x) cost(dx) 表示压缩 d x d_x dx 个字符得到的长度 c o s t ( d x ) { 1 , d x 1 2 , 2 ≤ d x ≤ 9 3 , 10 ≤ d x ≤ 99 4 , d x 100 cost(d_x) \begin{cases} 1, d_x 1 \\ 2, 2 \le d_x \le 9 \\ 3, 10 \le d_x \le 99 \\ 4, d_x 100\end{cases} cost(dx)⎩ ⎨ ⎧1,2,3,4,dx12≤dx≤910≤dx≤99dx100 实际上上述状态转移方程的复杂度非常高因为 X d X_d Xd 是一个非常大的集合我们枚举每一种方案是不现实的。
事实上如果 p 1 , … , p d x − 1 , i p_1, \dots, p_{d_x - 1}, i p1,…,pdx−1,i 是原串 s s s 中连续的出现字符 c x c_x cx 的位置不看其他字符那么方案数就没有这么多了。我们只需要枚举 d x d_x dx 就可以从 i i i 开始向左依次选取出现字符 c x c_x cx 的位置当选取了 d x − 1 d_x - 1 dx−1 次后即保留 d x d_x dx 个 c x c_x cx就对应着唯一的 p 1 , … , p d x − 1 , i p_1,\ \dots,\ p_{d_x - 1},\ i p1, …, pdx−1, i 。那么这样只考虑选择连续的 c x c_x cx 的做法是否正确呢 例如 s [ 1... i ] a a b c a s[1...i] aabca s[1...i]aabca 时我们要选择 2 2 2 个 a a a 其中一个 a a a 是 s [ i ] s[i] s[i] 我们如何保证只考虑选择连续的 a a a 即选择 a a ‾ b c a ‾ a \underline{a} bc\underline{a} aabca 而不考虑 a ‾ a b c a ‾ \underline{a} a b c \underline{a} aabca 这种情况中间隔了一个 a a a 呢 可以发现在 a ‾ a b c a ‾ \underline{a} a b c \underline{a} aabca 这种情况中我们保留了 2 2 2 个 a a a 而删除了 3 3 3 个字符。由于删除任意一个字符的代价都是一样的因此我们不如从左往右连续地保留 2 2 2 个出现的 a a a 而删除剩余的 3 3 3 个字符即 a ‾ a ‾ b c a \underline{a}\underline{a}bca aabca 这两种情况是等价的。而后者在 s [ 1... i ′ ] s [ 1...2 ] a a s[1...i] s[1...2] aa s[1...i′]s[1...2]aa 时就已经被考虑到因此我们不用考虑前者。 更直观地说如果我们选择的 d x d_x dx 个 c x c_x cx 不是连续的那么我们可以在对应的选择范围内从左到右连续地重新选择 d x d_x dx 个 c x c_x cx 二者是等价的。而后者由于连续性会在之前的状态转移中被考虑到。 因此我们可对状态转移方程进行优化只考虑选择连续的 c x c_x cx f [ i ] [ j ] min s [ i 0 ] s [ i ] { f [ i 0 − 1 ] [ j − d i f f ( i 0 , i ) ] c o s t ( s a m e ( i 0 , i ) ) } f[i][j] \min_{ s[i_0] s[i] } \{ f[i_0 - 1][j - diff(i_0, i) ] cost(same(i_0, i))\} f[i][j]s[i0]s[i]min{f[i0−1][j−diff(i0,i)]cost(same(i0,i))} 其中 d i f f ( i 0 , i ) diff(i_0, i) diff(i0,i) 表示 s [ i 0 … i ] s[i_0 \dots i] s[i0…i] 中与 s [ i ] s[i] s[i] 不同字符数目 s a m e ( i 0 , i ) same(i_0, i) same(i0,i) 表示 s [ i 0 … i ] s[i_0 \dots i] s[i0…i] 中与 s [ i ] s[i] s[i] 相同的字符数目有 d i f f ( i 0 , i ) s a m e ( i 0 , i ) i − i 0 1 diff(i_0, i) same(i_0, i) i - i_0 1 diff(i0,i)same(i0,i)i−i01 也就是说我们枚举满足 s [ i 0 ] s [ i ] c x s[i_0] s[i] c_x s[i0]s[i]cx 的 i 0 i_0 i0 选择所有在 [ i 0 , i ] [i_0, i] [i0,i] 范围内的 c x c_x cx 删除剩余的字符此时剩余的字符均不会是 c x c_x cx。
// cpp
class Solution {
public:int getLengthOfOptimalCompression(string s, int k) {auto calc [](int x) {if (x 1) return 1;if (x 10) return 2;if (x 100) return 3;return 4;};int n s.size();vectorvectorint f(n 1, vectorint(k 1, INT_MAX 1));f[0][0] 0;for (int i 1; i n; i) {for (int j 0; j k j i; j) { // 删除j个字符// 删除0个字符时要保留s[i-1]// 删除多个字符时考虑删除第i个字符和不删除第i个字符的情况if (j 0) f[i][j] f[i - 1][j - 1]; // 删除s[i-1]这个字符int same 0, diff 0; // diff统计不同的字符,都是要删除的for (int i0 i; i0 1 diff j; --i0) { // diffjif (s[i0 - 1] s[i - 1]) {same; // 删除[i0-1,i-1]中间的不同字符f[i][j] min(f[i][j], f[i0 - 1][j - diff] calc(same));} else {diff;}}}}return f[n][k];}
};// java
class Solution {private int calc(int x) {if (x 1) return 1;if (x 10) return 2;if (x 100) return 3;return 4;}public int getLengthOfOptimalCompression(String s, int k) {int n s.length();int[][] f new int[n 1][k 1];for (int i 0; i n; i) {Arrays.fill(f[i], Integer.MAX_VALUE 1);}f[0][0] 0;for (int i 1; i n; i) {for (int j 0; j k j i; j) {if (j 0) f[i][j] f[i - 1][j - 1];int same 0, diff 0;for (int i0 i; i0 1 diff j; --i0) {if (s.charAt(i0 - 1) s.charAt(i - 1)) {same;f[i][j] Math.min(f[i][j], f[i0 - 1][j - diff] calc(same));} else diff;}}}return f[n][k];}
}// python
class Solution:def getLengthOfOptimalCompression(self, s: str, k: int) - int:calc lambda x : 1 if x 1 else (2 if x 10 else (3 if x 100 else 4))n len(s)f [ [10**9] * (k 1) for _ in range(n 1)]f[0][0] 0for i in range(1, n 1):for j in range(min(k, i) 1):if j 0:f[i][j] f[i - 1][j - 1]same diff 0for i0 in range(i, 0, -1):if s[i0 - 1] s[i - 1]:same 1f[i][j] min(f[i][j], f[i0 - 1][j - diff] calc(same))else:diff 1if diff j:breakreturn f[n][k]复杂度分析
时间复杂度 O ( ∣ s ∣ 2 k ) O(|s|^2k) O(∣s∣2k) 其中 ∣ s ∣ |s| ∣s∣ 是原串 s s s 的长度。动态规划中状态的数目为 O ( ∣ s ∣ k ) O(|s|k) O(∣s∣k) 每一个状态需要 O ( ∣ s ∣ ) O(|s|) O(∣s∣) 的时间进行转移相乘即可得到总时间复杂度。空间复杂度 O ( ∣ s ∣ k ) O(|s|k) O(∣s∣k) 即为动态规划中状态的数目。
