bracket match
Nice and simple stack based solution:
1def 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:
1def bracket_match(text):
2 while text.count('()'):
3 text = text.replace('()', '')
4 return len(text)