CareerCup

Improvement on Raj's function:
public static bool FindGoodBadString(string s)
{
Stack st = new Stack();
bool returnTF = true;
if (s==null||s.Length <=1)
return false;
foreach (char c in s)
{
switch (c)
{
case '}':
if (st.Count == 0 || (char)st.Pop() != '{' )
returnTF = false;
break;
case '{':
st.Push(c);
break;
case '(':
st.Push(c);
break;
case ')':
if (st.Count == 0 || (char)st.Pop() != '(')
returnTF = false;
break;
default:
break;
}
if (!returnTF)
break;
}

if (returnTF && st.Count != 0)
returnTF = false;

return returnTF;
}

I hope stack will work in this case, When we get an opening bracket then we add that bracket in the stack. And when we get any closing bracket then we will check whether the top element of the stack is opening bracket of current closing otherwise there is some error.

I think it will work in all scenarios :

example 1 {abcdteeh} - we get opening bracket { then we put it into stack. And now keep traversing string. In end we get closing bracket now it is same type of bracket as of opening so it is gud string.

example (bans{xyzhs}aj)
stack ( {
and closing bracket order } ) so it is gud string

example }this{ - in this we get closing bracket when stack is empty, so bad string

example {abs{jeu} -
in this stack will left wid one element so again bad string

Any comments
s

what about we have too many brackets, say 100 G, ...

//Stack is the way to go
//Complexity: Log(N)

/// <summary>
/// Find good or bad string
/// </summary>
/// <param name="s"></param>
/// <returns>boolean = true or false</returns>
public static bool FindGoodBadString(string s)
{
Stack st = new Stack();
bool returnTF = true;

foreach (char c in s)
{
switch (c)
{
case '}':
if (st.Count == 0)
returnTF = false;
else if ((char)st.Pop() != '{')
returnTF = false;
break;
case '{':
st.Push(c);
break;
case '(':
st.Push(c);
break;
case ')':
if (st.Count == 0)
returnTF = false;
else if ((char)st.Pop() != '(')
returnTF = false;
break;
default:
break;
}
}

if (st.Count != 0)
returnTF = false;

return returnTF;
}

I don't see Raj's method is O(logN). He uses
foreach (char c in s).
This is clearly at least O(N).
First, have two array Left L[] and Right [];
start index = 0;
foreach (char c in s)
case '{': add 1 in L[]; lIndex++;
case '[': add 2 in L[]; lIndex++;
case '(': add 3 in L[]; lIndex++;
otherwise: do nothing.
reverse s or for each c in s, start from s.length-1 to 0 do
case '}': add 1 in R[]; RIndex++;
case ']': add 2 in R[]; RIndex++;
case ')': add 3 in R[]; RIndex++;
otherwise: do nothing.

Now, if Lindex != RIndex, it is a bad string.
Further more, for a good string we should have for every i: L[i] = R[RIndex-i-1].

Comparing to Raj's, the improved function has:
1. Take care of s=NULL or s.Length = 0 cases.
if (s==null||s.Length <=1)
return false; // if a single char is considered good, this won't work.
Suggestion:if (s==null||s.Length <1) return false;

2. A slightly better code:
if (st.Count == 0 || (char)st.Pop() != '(')
returnTF = false;

3. This is a good one inside switch:
if (!returnTF)
break; // stop if we already know it is not a good string

4. Check st.Count only if no error so far.
if (!returnTF)
break;

bool compare(stack<char>& st, char c)
{
..if ((c=='{')||(c=='[')||(c=='('))
....st.push(c);
..else{
....switch (c){
......case '}':
........if (st.top()=='{'){
..........st.pop();
..........return true;
........}
........else return false;
......case ']':
..........if (st.top()=='['){
............st.pop();
............return true;
..........}
..........else return false;
......case ')':
..........if (st.top()=='('){
............st.pop();
............return true;
..........}
..........else return false;
......default:
..........return true;
....}
..}
}

void main()
{
..stack<char> st;
..char* str="(bans{x[y]zhs}aj)";
..while (*str){
....if (compare(st, *str))
......str++;
....else
......break;
..}
..if (st.empty())
....cout<<"true";
..else
....cout<<"false";
}

Why do we need a stack ? Isnt it ok if i just increment a var when i find an opening brace and decrement it when i find a closing brace and at any point my count goes negative the string is bad.. else once i go through the entire string my count should be 0..

void printfGoodBad(const char * str)
{
int index = 0;
int goodBad = 0;
while(str[index] != '\0')
{
if(str[index] == '{' || str[index] == '(')
goodBad++;
else if(str[index] == '}' || str[index] == ')')
goodBad--;

if(goodBad < 0)
break;
index++;
}

printf("String %s is %s\n", str, goodBad ? "BAD" : "GOOD");
}

Just wanted to summarize.

Stack is the clue. use stack to find the matching braces. For all other validity check such a character, number in the string etc, go with your own test cases after seeking all the req from the interviewer.

Assuming the no. of brackets would be 10, so as to initialize my new array where I will store the special characters.

Alternative: Use a linked list to store the brackets.

{{
int GoodBadString(char str[])
{
int length=strlen(str);
int top=0, current=0;
int charList[10];

while(str[current]!='\0')
{
if(str[current]=='{')
{
charList[top]='}';
top++;
}

if(str[current]=='(')
{
charList[top]=')';
top++;
}
current++;

if(str[current]=='}' || str[current]==')')
if(str[current]==charList[top-1])
{
current++;
top--;
}
else
return 0;
}

if(top==0)return 1;
else
return 0;
}
}}

Assuming the no. of brackets would be 10, so as to initialize my new array where I will store the special characters.

Alternative: Use a linked list to store the brackets.

int GoodBadString(char str[])
{
int length=strlen(str);
int top=0, current=0;
int charList[10];

while(str[current]!='\0')
{
if(str[current]=='{')
{
charList[top]='}';
top++;
}

if(str[current]=='(')
{
charList[top]=')';
top++;
}
current++;

if(str[current]=='}' || str[current]==')')
if(str[current]==charList[top-1])
{
current++;
top--;
}
else
return 0;
}

if(top==0)return 1;
else
return 0;
}

Use two pointers. One starts from the beginning and one starts from the end. Stop when both of them encounter a bracket. Compare whether they are correspond. If not, bad string.
Else, keep increase and decrease the pointer until they meet. If they can meet, good string.

It is N.
Any one can think a log(N) method