CODILITY - LESSON 5 - Nesting

PROBLEM:

A string S consisting of N characters is called properly nested if:

• S is empty;
• S has the form "(U)" where U is a properly nested string;
• S has the form "VW" where V and W are properly nested strings.

For example, string "(()(())())" is properly nested but string "())" isn't.

Write a function:

class Solution { public int solution(string S); }

that, given a string S consisting of N characters, returns 1 if string S is properly nested and 0 otherwise.

For example, given S = "(()(())())", the function should return 1 and given S = "())", the function should return 0, as explained above.

MY INITIAL SOLUTION (87% score, time complexity O(N))

(click here to see the full test results at codility.com)

I did this solution in few different ways and all the time got 87% overall, missing one correctness test:

negative_match invalid structure, but the number of parentheses matches

0.061 s

WRONG ANSWER got 1 expected 0

class Solution { public int solution(string S) { int l = S.Length; int count=0; if (l == 0) return 1; foreach (char c in S) { if (c == '(') count++; else count--; } if (count ==0 && S[0]=='(' && S[l-1]==')') return 1; else return 0; } }

Until I realised I wasn't taking into account strings such as "( ( ) ( ) )" which has the right amount of pairs but it is wrongly nested. After this, it took me a while to realise the silly extra line that would correct this little error...

MY IMPROVED SOLUTION (100%, time complexity O(N))

(click here to see the full test results at codility.com)

class Solution { public int solution(string S) { // write your code in C# 6.0 with .NET 4.5 (Mono) int l = S.Length; int count=0; if (l == 0) return 1; foreach (char c in S) { if (c == '(') count++; else count--; if(count <0) return 0;//CORRECTING ABOVE ERROR! } if (count ==0 && S[0]=='(' && S[l-1]==')') return 1; else return 0; } }