題目連結:
題目意譯:
給定一由小寫字母組成之字串 S,一個複製字元之移除由選定兩個相鄰且相同的字元並移除它們所組成。
我們重複執行複製字元之移除於 S 上,直到我們再也無法移除任何字元。
回傳經由若干次的複製字元之移除後的最終字串。保證答案唯一。
注:
1 ≦ S.length ≦ 20000
S 只由小寫英文字母組成。
範例測資:
輸入: "abbaca"
輸出: "ca"
解釋:
例如,於 "abbaca" 中我們可以移除 "bb" ,因為該兩個字元相鄰且相同而且是唯一可能的選擇。該操作後的結果字串為 "aaca",其中 "aa" 為唯一可能,所以最終字串為 "ca"。
解題思維:
我們可以使用一個堆疊(Stack,不過使用 vector 或是 deque 這種雙端都可操作之容器也可以)來求得最終字串:
掃過字串 S ,每碰到一個字元就先判斷該字元是否與堆疊頂端(記得先檢查堆疊是否為空)的字元相同。
如果一樣,則將堆疊頂端的字元移除;反之,不一樣的話才將該字元放入堆疊中。
掃完後,堆疊內剩下的字元從底端到頂端就是最終字串之內容(因為是堆疊,所以從裡面取出來後還要反轉一次)。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。