2024-02-29|閱讀時間 ‧ 約 0 分鐘

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

題目敘述

題目會給我們一個字串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)

分享至
成為作者繼續創作的動力吧!
從 Google News 追蹤更多 vocus 的最新精選內容從 Google News 追蹤更多 vocus 的最新精選內容

作者的相關文章

小松鼠的演算法樂園 的其他內容

你可能也想看

發表回應

成為會員 後即可發表留言
© 2024 vocus All rights reserved.