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.
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
.
从字符串中移除星号。
给你一个包含若干星号 * 的字符串 s 。
在一步操作中,你可以:
选中 s 中的一个星号。
移除星号 左侧 最近的那个 非星号 字符,并移除该星号自身。
返回移除 所有 星号之后的字符串。注意:
生成的输入保证总是可以执行题面中描述的操作。
可以证明结果字符串是唯一的。来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/removing-stars-from-a-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路是 stack。如果遇到字母则入栈;遇到星号的时候,如果栈内有字母则弹出,没有字母则可以直接丢弃星号。
时间O(n)
空间O(n)
Java实现
1 class Solution { 2 public String removeStars(String s) { 3 Deque<Character> stack = new ArrayDeque<>(); 4 for (char c : s.toCharArray()) { 5 if (c == '*') { 6 if (!stack.isEmpty()) { 7 stack.pollLast(); 8 } 9 } else { 10 stack.offerLast(c); 11 } 12 } 13 StringBuilder sb = new StringBuilder(); 14 while (!stack.isEmpty()) { 15 sb.append(stack.pollFirst()); 16 } 17 return sb.toString(); 18 } 19 }
- LeetCode Removing String Stars 2390leetcode removing string stars 指针leetcode 2390 substrings leetcode removing minimum characters leetcode string extra leetcode largest number string difference leetcode string 2451 leetcode pieces obtain string 2390 partition leetcode optimal string leetcode anagrams string find