Sponsored
Sponsored
This approach utilizes a stack data structure to handle the character removals efficiently. As we iterate through the string, whenever a star (*) is encountered, we pop from the stack, effectively removing the last non-star character added. This allows us to handle both the star and its preceding non-star character in O(1) time.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), for the stack to hold characters.
1#include <stdio.h>
2#include <string.h>
3
4char* removeStars(char* s) {
5 int len = strlen(s);
6 char* stack = (char*)malloc(len + 1);
7 int top = 0;
8
9 for (int i = 0; i < len; ++i) {
10 if (s[i] == '*') {
11 if (top > 0) --top;
12 } else {
13 stack[top++] = s[i];
14 }
15 }
16
17 stack[top] = '\0';
18 return stack;
19}
20
21int main() {
22 char s[] = "leet**cod*e";
23 printf("%s\n", removeStars(s));
24 return 0;
25}The C implementation uses a character array as a stack to store non-star characters. We increment the top index when adding a character and decrement it when encountering a star, which effectively removes the most recent non-star character.
This alternative method involves using a simple two-pointer technique where we iterate through the string and build the result in place. We treat the string as a writable array and maintain a 'write' index that tells us where to place the next character. When we encounter a star, we just need to move the 'write' index back to overwrite the previous character.
Time Complexity: O(n)
Space Complexity: O(1), since operations are done in-place.
1
This Java solution uses a character array and two indices, read and write, to manage in-place modifications.