Solution to Codility lesson5 Brackets problem, link to Codility problem and complete solution at the end of the post.

**Definitions:**

*Properly nested* string S:

- S is empty;
- S has the form “
(U)” or “[U]” or “{U}” where U is a properly nested string;- S has the form “
VW” where V and W are properly nested strings.

** Problem:**Define a function

*solution*with input

*S*, such that

*solution*returns

*1*if string

*S*is properly nested and

*0*otherwise.

- Expected worst-case time complexity is
*O(N)*; - Expected worst-case space complexity is
*O(N)*(not counting the storage required for input arguments).

**Analysis:**

This problem is very similar to the Nesting problem. Only here we are going to use an actual stack to stack the characters. And similar to the Nesting problem, ‘(‘, ‘{‘, ‘[‘ will be a push, and ‘)’, ‘}’, ‘]’ will be a pop. But here we will have to analyse the return of the pop operation, and it will have to be the inverse of the symbol used for pop. If it is not we can return *0*. We can also return *0* if we pop an empty stack or if at the end of the iteration there still elements at the stack. Otherwise we can return 1.

Visiting every element of *S** *gives us a time complexity of* O(N)**.*

For the space complexity we have *O(N). *In the worst case the stack size will be *N//2* because in a properly nested string the numbers of elements ‘(‘, ‘{‘, ‘[‘ is equal to half the size of the string. And since we push for every ‘(‘, ‘{‘, ‘[‘, this can be the maximum size of the stack.

**Complete 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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
# Name: Brackets # Link: https://codility.com/demo/take-sample-test/brackets/ def solution(S): N = len(S) symbol_stack = stack(N//2 + 1) for k in xrange(N): # Push if he have a (, [ or { if S[k] == '{' or S[k] == '[' or S[k] == '(': # If we have a stack with half of the size of S the others chars must be ), ], or } if symbol_stack.size == N//2 + 1: return 0 symbol_stack.push(S[k]) # Pop the stack for ), ], } else: # If the stack is empty, S can't be properly nested if symbol_stack.size == 0: return 0 head = symbol_stack.pop() # If the head os the stack is different form the curretn reversed symbol S is not properly nested. if (not (head == '{' and S[k] == '}')) and (not (head == '[' and S[k] == ']')) and (not (head == '(' and S[k] == ')')): return 0 # If there if left elements at the stack at the end of the iteration S is not properly nested if symbol_stack.size > 0: return 0 # If we reach this point S is properly nested return 1 class stack(object): def __init__(self, N): self.size = 0 self._stack_ = [0] * N def push(self, x): self._stack_[self.size] = x self.size += 1 def pop(self): self.size -= 1 return self._stack_[self.size] def head(self): return self._stack_[self.size - 1] |

*Time Complexity O(N)*

*Space Complexity O(N)*