前往
大廳
主題

LeetCode - 1209. Remove All Adjacent Duplicates in String II 解題心得

Not In My Back Yard | 2021-05-29 00:00:03 | 巴幣 0 | 人氣 166

題目連結:


題目意譯:
給定你一個字串 s 以及一整數 k,一個 k-複製字元之移除由 s 中選定 k 個相鄰且相同的字元並移除它們所組成,使得刪除的子字串左側以及右側串接在一起。

我們重複執行 k-複製字元之移除於 s 上,直到我們再也無法移除任何字元。

回傳經由若干次的複製字元之移除後的最終字串。保證答案唯一。

限制:
1 ≦ s.length ≦ 10 ^ 5
2 ≦ k ≦ 10 ^ 4
s 只由小寫英文字母組成。



範例測資:
範例 1:
輸入: s = "abcd", k = 2
輸出: "abcd"
解釋: 沒有東西可以刪。

範例 2:
輸入: s = "deeedbbcccbdaa", k = 3
輸出: "aa"
解釋:
首先刪除 "eee" 和 "ccc",得到 "ddbbbdaa"
接著刪除 "bbb",得到 "dddaa"
最刪除 "ddd",得到 "aa"

範例 3:
輸入: s = "pbbcggttciiippooaais", k = 2
輸出: "ps"


解題思維:
我們可以仿照上一題的想法——使用堆疊(Stack)儲存先前的字元,但是本題還需要儲存先前的「連續」字元群的長度(或是該群從哪個位置開始的)。

當目前字元跟堆疊頂端的字元一樣就忽略;當字元不一樣時,判斷目前的位置與堆疊頂端(也就是前一群連續字元)是否相差 k 個字元遠,如果是則將堆疊頂端移除(代表我們要刪除前一群)。之後將目前字元放入堆疊裡。

最後堆疊裡剩下的字元(記住,我們還有長度的資訊,所以這些字元可能需要重複多次)即是所求的最終字串。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作