bracket match

Go Back home

Nice and simple stack based solution:

 1 def bracket_match(text):
 2   # time: amortized O(n)
 3   # space: number unmached -> best O(1), worst: O(n)
 4   s = []      
 5   for c in text:
 6       if c == ')' and len(s) and s[-1] == '(':
 7         s.pop()
 8       else:
 9         s.append(c)
10   return len(s)

If complexity isn't too much of an issue:

1 def bracket_match(text):
2   while text.count('()'):
3     text = text.replace('()', '')
4   return len(text)