推 Rushia: 大師 hard 我漬鯊 10/15 19:02
推 oooptt: 大師 10/15 19:03
推 NTHUlagka: 哇靠 這太神了吧 10/16 12:37
1531. String Compression II
給你一個字串和能刪除的字元數 問刪除後再 string compression 的最短長度
string compression 的例子: "aa" -> "a2", "aaabcccd" -> "a3bc3d"
Example:
Input: s = "aaabcccd", k = 2
Output: 4
將 s 刪除 "b" 和 "d" 變成 "aaaccc" 後 compress 成 "a3c3"，長度為4
思路:
1.看到這種給字串然後進行 k 個操作的 就先嘗試用 dp 解
index 就是現在操作到哪和 k 剩多少 這題的 k 對應到的就是還能刪除的字元數
ex: dp[i+1][k-1] = min(dp[i+1][k-1], dp[i][k]) #刪除s[i]
dp[i+1][k] = min(dp[i+1][k], dp[i][k]保留s[i]後的長度 ) #保留s[i]
dp[i][k] 代表操作到 s[0:i] 並且還能刪除 k 個字元狀況下的最短長度
2.上面保留 s[i] 後的長度會和前一個字元有關 比如 "aaba" 刪除 "b" 後會變成 "aaa"
所以除了操作到哪還要考慮前一個字元是什麼 這樣才能正確算出 compress 後的長度
3.這裡就有幾種作法 一種是把前一個字元的資訊也當成 dp table 的 index
或是 recursive function 的 argument
一種是在操作 s[i] 時更新多一點 把操作從要不要刪除這個字元
改成刪除 s[i:j] 中出現次數最多的字元以外的字元 也就是保留單一字元下的最佳解
ex: s[i:j] = "aabacad" -> "aaaa", 刪除字數=4
因此 dp[j][k-4] = min(dp[j][k-4], dp[i][k] + len("a4"))
這樣就能在保證檢查到所有狀況的同時不用考慮前一個字元的資訊
4.所以最後的做法就是 dp[i][k] 代表操作完 s[0:i] 的最短長度，還能刪除 k 個
對 j = i~len(s) 去更新 dp[j][k-刪除字元數]
刪除字元數就是區間長度 j - i + 1 減掉出現次數最多的字元數 most
要加上的長度就看 most 是幾次 a -> 1, a9 -> 2, a10 -> 3, a100 -> 4
所以可以寫成 1 + (most>1) + (most>9) + (most>99)
另外雖然直接刪除 s[i] 的狀況已經被前面包含到了
不過為了 cover 從頭開始刪的狀況還是要額外寫出來
Python code:
class Solution:
def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
n = len(s)
dp = [[float('inf')]*(k+1) for _ in range(n+1)]
dp[0] = [0]*(k+1)
for i in range(k, -1, -1):
for j in range(n):
count = defaultdict(int)
if i > 0:
dp[j+1][i-1] = min(dp[j+1][i-1], dp[j][i])
for m in range(j, n):
count[s[m]] += 1
most = max(count.values())
delete = m - j + 1 - most
if delete <= i:
dp[m+1][i-delete] = min(dp[m+1][i-delete], dp[j][i] +
1 + (most>1) + (most>9) + (most>99))
else:
break
return dp[n][0]
出大事了 我自己寫的我都快看不懂了
--
可憐
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.214.153 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1665831584.A.581.html