題目連結:
題目意譯:
給定你一個字串 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 個字元遠,如果是則將堆疊頂端移除(代表我們要刪除前一群)。之後將目前字元放入堆疊裡。
最後堆疊裡剩下的字元(記住,我們還有長度的資訊,所以這些字元可能需要重複多次)即是所求的最終字串。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。