Re: [閒聊] 每日LeetCode
1531. String Compression II
https://leetcode.com/problems/string-compression-ii/description
給你一個字串s 和一個整數 k，字串壓縮為把字串相鄰的字元壓縮成字元和數量
，例如： a -> a bb -> b2 ccc -> c3，我們可以從 s 裡面刪除 k 個字元，求
出壓縮後的字串最小長度是多少。
思路：
1.很明顯的 DP 題，狀態轉移方程式是 DP(n, m) 表示長度為 n 的字串可以刪除
m 個字元可以得到的最大長度，初始化為 s 的字串長。
2.困難點是狀態轉移方程的推導，可分成兩個 CASE：
Case 1:
如果刪除次數剩餘大於0，且我們不壓縮當前字串（刪除當前字串），那麼長度就會是
次數減一且長度減一的最小壓縮長度 = DP(n - 1, m - 1)。
Case 2:
或者我們可以從當前字元往前壓縮，假設當前位置為 i 且在 i 之前的不同字元數量少
於等於 k，那麼我們就可以把所有不同的字元刪除得到一個壓縮串，例如：
aababaa 有5個a兩個b，如果k大於2就可以刪掉所有不為a的字元得到一個 a5。
假定取出壓縮後的字串長度函數是 compress，因為最佳解可能是很多種壓縮方式的組
合，所以我們要遍歷所有的合法壓縮方式：
MIN(
compress(a) + "aababa"的最佳長度,
compress(aa) + "aabab"的最佳長度,
compress(baa) + "aaba"的最佳長度,
...,
compress(aababaa)
)
這兩個Case取最小值就是當前位置可得的最佳長度，做到dp[n][k] 即可。
Java Code：
---------------------------------------------------
class Solution {
public int getLengthOfOptimalCompression(String s, int k) {
int n = s.length();
if (n == 0) {
return 0;
}
int[][] dp = new int[n + 1][k + 1];
for (int i = 0; i <= n; i++) {
Arrays.fill(dp[i], n);
}
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= Math.min(i, k); j++) {
if (j > 0) {
dp[i][j] = dp[i - 1][j - 1];
}
int same = 0;
int notSame = 0;
for (int ii = i; ii >= 1; ii--) {
if (s.charAt(i - 1) == s.charAt(ii - 1)) {
same++;
} else {
notSame++;
}
if (j >= notSame) {
dp[i][j] = Math.min(dp[i][j], dp[ii - 1][j - notSame]
+ compress(same));
}
}
}
}
return dp[n][k];
}
private int compress(int x) {
if (x >= 100) return 4;
if (x >= 10) return 3;
if (x >= 2) return 2;
return 1;
}
}
---------------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1703775457.A.D14.html
推
12/28 23:00,
1年前
, 1F
12/28 23:00, 1F
推
12/28 23:01,
1年前
, 2F
12/28 23:01, 2F
推
12/28 23:02,
1年前
, 3F
12/28 23:02, 3F
推
12/28 23:04,
1年前
, 4F
12/28 23:04, 4F
※ 編輯: Rushia (122.100.73.13 臺灣), 12/28/2023 23:09:46
推
12/28 23:11,
1年前
, 5F
12/28 23:11, 5F
討論串 (同標題文章)
完整討論串 (本文為第 588 之 719 篇)：