題目會給我們一個字串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只會包含小寫英文字母 和 *星號。
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)