大家好,欢迎来到无限大的频道。
今日继续给大家带来力扣题解。
题目描述(中等):
从字符串中移除星号
给你一个包含若干星号 * 的字符串 s 。
在一步操作中,你可以:
-
-
-
选中 s 中的一个星号。
-
移除星号 左侧 最近的那个 非星号 字符,并移除该星号自身。
-
-
返回移除 所有 星号之后的字符串。
注意:
-
-
-
生成的输入保证总是可以执行题面中描述的操作。
-
可以证明结果字符串是唯一的。
-
-
解题思路:
我看到这个题,思路就是直接抽象,题目要求的就是字符串当中的星号和非星号区分开来,每当遇到一个星号时,移除前面最近的一个字符。这种行为可以被抽象为一个栈的操作,当遇到字符时,将其压入栈中;当遇到星号时,从栈中弹出一个字符。(作为一个中等题来说,多少有些简单了)
-
使用栈结构:我们可以使用一个栈来存储字符串中的字符。栈的顶端代表最近添加的字符。
-
遍历字符串:遍历给定的字符串 s:
-
如果遇到一个普通字符(非星号),将其压入栈中。
-
如果遇到一个星号(*),则从栈中弹出一个字符(如果栈不为空)。
-
-
重建字符串:遍历完字符串后,栈中剩下的字符就是移除星号后所需的字符串。将这些字符复制回原始字符串 s 中,并在末尾添加字符串结束符 \0。
-
释放内存:最后,释放用于存储栈的动态分配内存。
参考代码:
char* removeStars(char* s) {
char* stack = malloc(strlen(s) + 1);
int top = -1;
for(int i = 0;s[i] != '\0'; i++){
if (s[i] != '*'){
stack[++top] = s[i];
}else{
if (top != -1){
top--;
}
}
}
for (int i = 0; i <= top; i++){
s[i] = stack[i];
}
s[top + 1] = '\0';
free(stack);
return s;
}
时间复杂度:
-
-
-
遍历字符串:字符串的长度为 n,我们需要遍历每个字符一次,因此这一部分的时间复杂度为 O(n)。
-
重建字符串:在遍历完字符串后,我们还需要将栈中的字符复制回字符串中,这也是 O(n) 的操作。
-
-
综上所述,整体时间复杂度为 O(n)。
空间复杂度:
-
-
-
栈的使用:我们使用了一个与输入字符串长度相同的栈来存储字符,最坏情况下(没有星号的情况下),栈的大小可以达到 n。
-
额外的空间:除了栈之外,算法没有使用其他显著的额外空间。
-
-
因此,空间复杂度为 O(n)。