Skip to content

LeetCode: 2390-Removing Stars From a String 解題紀錄

Last Updated on 2023-04-11 by Clay

題目

ou are given a string s, which contains stars *.

In one operation, you can:

  • Choose a star in s.
  • Remove the closest non-star character to its left, as well as remove the star itself.

Return the string after all stars have been removed.

Note:

  • The input will be generated such that the operation is always possible.
  • It can be shown that the resulting string will always be unique.

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 來操作,想說依序檢查字元,如果是 * 就直接 pop 出最後一項、如果不是則存入字元。

但是後來發現,我要將 stack 的字元拼回字串需要再次顛倒順序,反而花費的時間讓我遇到 TLE 超時問題。

最後換成使用陣列直接來做。


儲存每一個字元 複雜度

Time ComplexityO(n)
Space ComplexityO(n)


C++ 範例程式碼

class Solution {
public:
    string removeStars(string s) {
        // Init
        vector<char> v;

        // Detect '*' and pop the previous character
        for (char c: s) {
            if (c != '*') {
                v.emplace_back(c);
            }
            else {
                v.pop_back();
            }
        }

        // Convert `vector` into `string`
        string result(v.begin(), v.end());
        return result;
    }
};



Python 範例程式碼

class Solution:
    def removeStars(self, s: str) -> str:
        # Init
        v = []

        # Detect '*' and pop the previous character
        for c in s:
            if c == '*' and v:
                v.pop()
            else:
                v.append(c)

        # Convert `vector` into `string`
        return "".join(v)



移動節點

另一個方法比較巧妙,是第一個方法的改進,但是就不需要另外儲存字元了。

其道理非常單純:我們照樣遍歷原始字串,但同時更新一個節點值 i

這個節點值 i 初始值同樣為 0,在遇到 * 符號前跟遍歷原始字串的索引值是一模一樣的;但是在遇到 * 符號時,便需要將該節點值 i 減去 1,除此之外的情況,則是 s[i] = 當前遍歷到的字元。

下面舉第一個範例來一步步操作。其中 i 是節點值,j 是當前字串的索引值。

Example1: leet**cod*e
012345678910
leet**cod*e

i=0, j=0, curr=l
l

i=1, j=1, curr=e
le

i=2, j=2, curr=e
lee

i=3, j=3, curr=t
leet

i=3-1=2, j=4, curr=*
leet

i=2-1=1, j=5, curr=*
leet

i=2, j=6, curr=c
lect

i=3, j=7, curr=o
leco

i=4, j=8, curr=d
lecod

i=4-1=3, j=9, curr=*
lecod

i=4, j=10, curr=e
lecoe


之後只需要取 [0, i] 的字串範圍當作新字串即可。


移動節點 複雜度

Time ComplexityO(n)
Space ComplexityO(1)


C++ 範例程式碼

class Solution {
public:
    string removeStars(string s) {
        // Init
        int i = 0;
        
        // Detect '*' and pass the previous stored character
        for (char c: s) {
            if (c == '*') {
                --i;
            }
            else {
                s[i++] = c;
            }
        }

        // Convert `vector` into `string`
        return s.substr(0, i);
    }
};



Python 範例程式碼

class Solution:
    def removeStars(self, s: str) -> str:
        # Init
        s = list(s)
        i = 0
        
        # Detect '*' and pass the previous stored character
        for c in s:
            if c == '*':
                i -= 1
            else:
                s[i] = c
                i += 1

        # Convert `vector` into `string`
        return "".join(s[:i])

References


Read More

Leave a Reply