'Unable to pass all test cases-> string problem with use of stack data structure in C
Regarding this leetcode problem
My solution: I am pushing all characters in a string to a stack data structure. While pushing I keep track of the number of '(' and ')' using count, which increments for '(' and decrements for ')'. I try to maintain the count as zero by popping ')' from stack when it is negative. After going through the entire loop, if count is positive, then I try to remove '(' going over the stack. And I store the result in variable res.
This is above approach is not working for some test cases. Can you point out the issues with my code?
I have not tried to improve the performance yet. I just wanted to get this initial code working with all cases.
typedef struct stack
{
char *data;
int topIndex;
int total;
}stack;
stack *st;
void stackPush(char x)
{
st->topIndex++;
st->data[st->topIndex] = x;
}
char stackPop()
{
char a = 0;
if(st->topIndex > -1)
{
a = st->data[st->topIndex];
st->topIndex--;
}
return a;
}
char * minRemoveToMakeValid(char * s){
int l = strlen(s);
char r;
char *res = (char *) malloc(sizeof(char)*(l+1));
st = (stack*)malloc(sizeof(stack));
st->data = (char*) malloc(sizeof(char)*(l));
st->topIndex = -1;
int count = 0;
int j = 0;
int u =0;
// maintain count as zero, if negative try to pop.
while(j < l)
{
if(s[j] == '(')
{
count++;
}
else if(s[j] == ')')
{
count--;
}
stackPush(s[j]);
if(count < 0)
{
count++;
stackPop();
}
j++;
}
u = st->topIndex;
res[u+1] = '\0';
// if count is greater than zero, try to bring it down to zero by popping '('
while ((st->topIndex > -1))
{
r = stackPop();
if(((count > 0) && (r == '(')))
{
count--;
}
else
{
res[u] = r;
u--;
}
}
// wanted to initialize res to empty string in case the test case is "))(("
if(u > st->topIndex)
{
res = "";
}
return res;
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
