付費限定文章

堆疊應用+模擬: 移除字串中的星號_Leetcode 精選75題解析

Daniel Olah on Unsplash

題目敘述

題目會給我們一個字串s。

要求我們移除字串中的星號，還有刪除星號左手邊最靠近的第一個字元。

以字串的形式返回輸出答案。

題目的原文敘述

測試範例

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 <= 10^5

字串s的長度介於 1 ~ 10^5 之間。

• s consists of lowercase English letters and stars *.

字串s只會包含小寫英文字母 和 *星號。

• The operation above can be performed on s.

定義中的操作可以在字串s中完成。

演算法

這題的關鍵在於把 *星號 當成我們平常鍵盤上使用的←Backsapce鍵的功能，向左邊吃掉一個最靠近的字元。

實作的時候，先建立一個空的stack，把每個字元依序推入stack。
假如遇到 *星號，則直接pop stack頂端的字元，相當於滿足題目所說的「向左邊吃掉一個最靠近的字元」。

最後，把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)