Solution to Brackets by codility

26 Replies to “Solution to Brackets by codility”

1. Ruby Version

   1 2 3 4 5 6 7 8 9 10 11 12 13

   def solution(s)   stack = []   matches = {'}' => '{', ']' => '[', ')' => '('}   s.each_char do |c|     if c =~ /[[({]/       stack.push(c)     else       return 0 if stack.length == 0 || matches[c] != stack.pop     end   end   return 1 if stack.length == 0   return 0 end

   Reply

   • oops, how do I embed code in a comment?

     Reply

     • Thanks for your sharing! Please place the code inside a <pre> </pre> block.

       Reply

2. C# Solution.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

   using System; using System.Collections; using System.Collections.Generic; namespace Codility {     class Program     {          public int solution(string S)           {             Dictionary matched = new Dictionary();             matched.Add("]", "[");             matched.Add("}", "{");             matched.Add(")", "(");             List to_push= new List();             to_push.Add("[");             to_push.Add("{");             to_push.Add("(");             Stack stack = new Stack();             foreach (char c in S)             {                 if (to_push.Contains(c.ToString()))                     stack.Push(c.ToString());                 else                     if (stack.Count == 0)                         return 0;                     else if (!stack.Pop().Equals(matched[c.ToString()]))                     {                         return 0;                     }             }             if (stack.Count == 0)                 return 1;             return 0;        } } }

   Reply

   • Thanks for sharing!

     Reply

3. I don’t know if you’ve tested this in a IDE, but this is the correct C# solution 100%:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

   public int Solution(string S)         {             Dictionary matched = new Dictionary();             matched.Add("]", "[");             matched.Add("}", "{");             matched.Add(")", "(");             List pushElement = new List();             pushElement.Add("[");             pushElement.Add("{");             pushElement.Add("(");             Stack stack = new Stack();             foreach (char c in S)             {                 if (pushElement.Contains(c.ToString()))                     stack.Push(c.ToString());                 else                     if (stack.Count == 0)                         return 0;                     else if (!stack.Pop().Equals(matched[c.ToString()]))                     {                         return 0;                     }             }             if (stack.Count == 0)                 return 1;             return 0;         }

   Reply

   • Thanks for sharing! I tested my code in both local IDE and Codility.com.

     Reply

     • Above code had compilation errors even algorithm is correct but does not compile correctly. I will suggest the code below:

       1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

       using System; using System.Collections; using System.Collections.Generic; class Solution {     public int solution(string S) {         // write your code in C# 6.0 with .NET 4.5 (Mono)          Dictionary<string, string> matched = new Dictionary<string, string>();             matched.Add("]", "[");             matched.Add("}", "{");             matched.Add(")", "(");             List<string> pushElement = new List<string>();             pushElement.Add("[");             pushElement.Add("{");             pushElement.Add("(");             Stack stack = new Stack();             foreach (char c in S)             {                 if (pushElement.Contains(c.ToString()))                     stack.Push(c.ToString());                 else                     if (stack.Count == 0)                         return 0;                     else if (!stack.Pop().Equals(matched[c.ToString()]))                     {                         return 0;                     }             }             if (stack.Count == 0)                 return 1;             return 0;     } }

       See the results for this over the codility:
       https://codility.com/demo/results/demo4KD3BK-X89/

       Reply

       • Thank you!

         Reply

       • Interestingly, in C#, if you use generic

         1	var stack = new System.Collections.Generic.Stack<int>();

         to avoid all “.ToString()”s same code will fail on codility.com by performance – shows only 40%. Changing it back to

         1	System.Collections.Stack()

         gives 100%.

         Reply

4. I was talking about Kaiser’s solution. Apparently “<pre>” tag somehow formatted my Dictionary<string,string> VS 2013 won’t recognize Dictionary as a Generic Collection

   Reply

   • I do not know VS very much. But probably you cannot directly copy some code in the comment section, because they escape some HTML Character Entities like < and >.

     Reply

   • it’s because you have to add :
     using System.Collection.Generic.
     Another working solution in csharp :
     https://codility.com/demo/results/demoDHU8ZZ-DBB/

     Reply

     • Thanks for your explanation!

       Reply

5. This works same as a stack and it is a bit shorter (still O(n)):

   1 2 3 4 5 6 7 8 9 10 11 12 13

   def solution(S):     A = [""]*(len(S)+1)     top = 0     for s in S:         if (s == ')' and A[top] == '(') or (s==']' and A[top]=='[') or (s=='}' and A[top]=='{'):             top -= 1         else:             top += 1             A[top] = s     if top==0:         return 1     else:         return 0

   Reply

   • Good idea. Actually you are doing a stack by your self.
     For the other readers with other programming languages, please notice that the top pointer might be negative value. For example, the test input might be “)))”.

     Reply

   • Very nice solution!

     Reply

6. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

   // you can use includes, for example: // #include <algorithm> // you can write to stdout for debugging purposes, e.g. // cout << "this is a debug message" << endl; #include <stack> bool bracketFound(char c, char brackets[]); bool bracketsMatch(char close, char brackets[], char open); int solution(string &S) {     // write your code in C++11     const int N = S.length();     if (N == 0) return 1; // empty string     if (N%2 != 0) return 0; // odd number of chars     // tracks the last opened brackets     std::stack<char> openedBrackets;     char opened[] = {'{', '[', '('};     char closed[] = {'}', ']', ')'};     for(int i=0; i <N; i++){         // save opening bracket in stack         if(bracketFound(S[i], opened)) openedBrackets.push(S[i]) ;         // closing bracket         else{             if(openedBrackets.empty()) return 0;             // Check if brackets are complementary             string M("");             M = M + openedBrackets.top() + S[i];             if (M != "{}" && M != "[]" && M != "()") return 0;             // pop elements when closing             openedBrackets.pop();         }     }     // ensure that stack is empty     if(openedBrackets.empty()) return 1;     else return 0; } bool bracketFound(char c, char brackets[]){     for(int i = 0; i < 3; i++) if(c == brackets[i]) return true;     return false; }

   Reply

7. Here’s a Java 100/100 Solution:
   https://codility.com/demo/results/demo97TPVG-CPP/

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

   import java.util.List; import java.util.ArrayList; import java.util.Map; import java.util.HashMap; class Solution {     public static final int BALANCED = 1;     public static final int UNBALANCED = 0;     public int solution(String S) {         if (S.isEmpty()) return BALANCED;         Stack<Character> stack = new Stack<>(S.length());         NestedValidatorUtil util = new NestedValidatorUtil();         for (char c: S.toCharArray()) {             if (stack.isEmpty()){                 if (util.isOpener(c)) {                     stack.push(c);                 } else {                     return UNBALANCED;                 }             } else {                 if(util.isOpener(c)) {                     stack.push(c);                 } else if(util.getOpenerForGivenCloser(c) == stack.peek()){                     stack.pop();                 } else {                     return UNBALANCED;                 }             }         }         return stack.isEmpty() ? BALANCED : UNBALANCED;     }     public static class NestedValidatorUtil {         private Map<Character, Character> language = new HashMap<Character, Character>(){{             put(')','(');             put(']','[');             put('}','{');             }};         public boolean isOpener(Character c) {             return language.values().contains(c);         }         public Character getOpenerForGivenCloser(Character closer) {             return language.get(closer);         }     }     public static class Stack<T> {           public List<T> stack;           public Stack(int capacity) {               stack = new ArrayList<>(capacity);           }           public void push(T item) {               stack.add(item);           }           public T pop() {               T item = peek();               stack.remove(stack.size() - 1);               return item;           }           public T peek() {               int position = stack.size();               T item = stack.get(position - 1);               return item;           }           public boolean isEmpty() {               return stack.isEmpty();           }       } }

   Reply

8. A C# solution:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

   using System; using System.Collections; public int solution(string S) {         // write your code in C# 6.0 with .NET 4.5 (Mono)         var stack = new Stack();         for (var i=0; i<S.Length; i++)         {             if (stack.Count == 0)                 stack.Push(S[i]);             else{                 if (IsPair((char)stack.Peek(), S[i]))                     stack.Pop();                 else                     stack.Push(S[i]);             }         }         return stack.Count == 0 ? 1 : 0;     }     bool IsPair(char c1, char c2)     {         if (c1 == '{') return c2 == '}';         if (c1 == '(') return c2 == ')';         if (c1 == '[') return c2 == ']';         return false;     }

   Reply

9. I’m surprised so few people didn’t do a simple modulo at the start to check whether there is an even number of chars. In production, you wouldn’t want this algorithm to run against a big string and only terminate at the end when one closing token is missing. You’d want it to terminate as soon as it’s possible

   Reply

   • Much appreciate your comment and suggestion!

     Reply

10. Py:

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

    def solution(S):     if len(S) % 2 == 1:         return 0     active = []     openers = ["(","[","{"]     closers = [")","]","}"]     for e in S:         if e in openers:             active.append(closers[openers.index(e)])         elif len(active) == 0 or active.pop() != e:             return 0     if len(active) == 0:         return 1     else:         return 0

    Reply

11. Swift solution 100%

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

    func solution(_ S: String) -> Int {     // empty string     if S.count == 0 { return 1 }     var stack: [Character] = []     for char in S {         switch char {         case "{":             stack.append(char)         case "[":             stack.append(char)         case "(":             stack.append(char)         default:             if stack.count == 0 { return 0 }             let lastChar = stack.popLast()!             switch (lastChar, char) {             case ("{", "}"):                 continue             case ("[", "]"):                 continue             case ("(", ")"):                 continue             default:                 return 0             }         }     }   if stack.count != 0 {         return 0     }       return 1 }

    Reply

12. Completely uneccessary solution using numbers. Python solution – O(N).

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

    def solution(S):          bracket_map = {"{":10,"}":-10,"[":20,"]":-20,"(":30,")":-30}          #check if even number of brackets     N = len(S)     if N == 0: return 1     if N % 2 != 0: return 0          #mapped_list     S_map = [bracket_map[i] for i in S]     nested = []          #while loop to check symmetry of brackets not closing in instantyl     i = 0     while i < N-1:         diff = S_map[i+1] + S_map[i]         if diff == 0 and S_map[i+1] < S_map[i]:             #nested += [0]*2             i += 2         else:             nested += [S_map[i]]             nest_len = len(nested)             if (nest_len > 1 and nested[nest_len-1] < nested[nest_len-2]) and nested[nest_len-1] + nested[nest_len-2] == 0:                 nested.pop(nest_len-1)                 nested.pop(nest_len-2)             i += 1                  nested.append(S_map[-1])          #check symmetry     N_map = len(nested)     left_map = nested[:int(N_map/2)]     right_map = nested[-1:int(-1*N_map/2)-1:-1]          #check condition of order of occurrence (close cannot occur before open)     cond_check = 0     for i, j in zip(left_map, right_map):         if i+j == 0 and i > j:             cond_check += 1                  if int(N_map/2) == cond_check:         return 1     else:         return 0

    Reply

13. Thanks for this blog post! I was banging my head against the wall thinking this is a simple / short solution, where you just build a stack and scan each item popped for validity.
    Your solution is way more elegant than mine but I set out not to use anything as complex as a dictionary.

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

    def nested(S):     if len(S) == 0:         return 1     if len(S) % 2 != 0:         return 0     # Stack represents unsolved business, brackets waiting to be closed.     stack = []     o = ["(", "[", "{"]     c = [")", "]", "}"]     l = [S[i] for i in range(len(S))]     for i in l:         # First, filter: does it get stacked or not? Only gets stacked if previous in stack not         # forming a pair         # or if it is an open         # bracket.         if i in c:             if len(stack) == 0:                 return 0             if stack[-1] in o:                 if c.index(i) == o.index(stack[-1]):                     stack.pop()                 else:                     return 0             else:                 stack.append(i)         else:             stack.append(i)     if len(stack) == 0:         return 1     else:         return 0

    Reply