題目敘述
題目會給定一個字串s，把裡面的星號*視為鍵盤上的backspace，往前(往左方)吃掉最靠近的字元。
請位最後全部操作完以後，剩下的字串內容為何?例如:
abc**，最後剩下a。
說明:
bc分別被右邊的星號給吃掉。
測試範例
Example 1:
Input: s = "leet**cod*e"
Output: "lecoe"
Explanation: Performing the removals from left to right:
- The closest character to the 1st star is 't' in "leet**cod*e". s becomes "lee*cod*e".
- The closest character to the 2nd star is 'e' in "lee*cod*e". s becomes "lecod*e".
- The closest character to the 3rd star is 'd' in "lecod*e". s becomes "lecoe".
There are no more stars, so we return "lecoe".
Example 2:
Input: s = "erase*****"
Output: ""
Explanation: The entire string is removed, so we return an empty string.
約束條件
Constraints:
1 <= s.length <= 105sconsists of lowercase English letters and stars*.- The operation above can be performed on
s.
演算法
這題基本上和stack配對模型可說是互為表裡，完美搭配。
邏輯上很直覺，也很好懂。
從左到右，依序掃描每個字元。
如果遇到普通字元，直接推入stack。
如果遇到星號*，相當於我們鍵盤上的backspace 往前吃字元的功能，從stack pop出頂端的元素。
最後，留在stack內部的字元，串接在一起轉成字串，就是答案囉!
程式碼
class Solution:
def removeStars(self, s: str) -> str:
stk = []
# scan each character from left to right
for char in s:
if char != '*':
# push current character into stack
stk.append( char )
else:
# pop one character from stack, removed with * together.
stk.pop()
return "".join(stk)
複雜度分析
時間複雜度: O( n )
從頭到尾，每個字元檢查過一遍。
空間複雜度: O( n )
需要一個stack，stack耗用空間最多和字串長度一樣長。
關鍵知識點
在於理解並且活用stack 先進後出FILO的特質，來實作*星號和普通字元的配對。
記得回去複習 合法括號配對、最長合法括號配對字串長度 這兩題，主要的原理是相通的。
Reference:
[1] Python/JS/C++ O(n) by stack [w/ Explaination] 有 中文詳解 解題影片 - Removing Stars From a String - LeetCode
