一魚多吃 用stack來解 移除星號 Removing Stars_Leetcode #2390

這題的題目在這裡:

題目敘述

題目會給定一個字串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 <= 105
• s consists 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