2390. Removing Stars From a String

[songyy5517]

You 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.

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.

Intuition This problem mainly examines String. We need to remove the character before every asterisk. A simple idea is to loop through the string. For each character, if it is a non-asterisk character, then we add it to the StringBuffer; otherwise, we delete the last character in the StringBuffer.

[songyy5517]

Approach: Loop through the String

1. Exception handling;
2. Define a StringBuffer to store each character;
3. Loop through the string: （1）If the current character is an asterisk, then remove the last character in the StringBuffer; （2）Otherwise, add this character to the StringBuffer.
4. Convert the StringBuffer to String, and return.

Complexity Analysis

• Time complexity: $O(N)$ , looping through the entire string takes $O(N)$ time;
• Space complexity: $O(N)$ , additionally define a StringBuffer which takes $O(N)$ space.

[songyy5517]

class Solution {
    public String removeStars(String s) {
        // Intuition: Consider StringBuffer as Stack.
        // 1. Exception handling
        if (s == null || s.length() == 0)
            return "";

        // 2. Define stack
        StringBuffer res = new StringBuffer();
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (c == '*' && res.length() != 0)
                res.deleteCharAt(res.length() - 1);
            else 
                res.append(c);
        }

        return res.toString();
    }
}

[songyy5517]

2024/5/21