1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public String removeStars(String s) {
StringBuilder ans = new StringBuilder();
int starCount = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '*') {
starCount += 1;
} else {
if (starCount == 0) {
ans.append(s.charAt(i));
} else {
starCount -= 1;
}
}
}
return ans.reverse().toString();
}
}
|
倒着遍历. 很像之前有道题, 就是#表示backspace那道题.
时间复杂度: O(n)
空间复杂度: O(n) 因为用了stringbuilder.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public String removeStars(String s) {
int left = 0, right = 0;
StringBuilder ans = new StringBuilder(s);
while (right < s.length()) {
if (s.charAt(right) != '*') {
ans.setCharAt(left, s.charAt(right));
left += 1;
} else {
left -= 1;
}
right += 1;
}
return ans.substring(0, left);
}
}
|
还有种写法, 双指针, 也挺有意思的. 但是我在想如果很多***呢? 题目约束就是肯定有东西和它抵消.
思路就是right遇到不是星的, left这个位置就放这个right指向的这个char. 然后更新left和right, 如果right指向的是星, 那么left这边就要被抵消掉一个, 于是left -= 1. left始终指向的是下一个right找到的非星char的位置. 因此最后, 我们取(0, left), 也就是left左边都是放好的, 就取它们.
时间复杂度: O(n)
空间复杂度: O(n) 如果是c++, 可以在string上改东西, 那时间复杂度就是O(1)了.
