# Bracket matcher in Python

I would like to receive feedback on my coding interview for the following problem:

### Bracket Match

A string of brackets is considered correctly matched if every opening bracket in the string can be paired up with a later closing bracket, and vice versa. For instance, “(())()” is correctly matched, whereas “)(“ and “((” aren’t. For instance, “((” could become correctly matched by adding two closing brackets at the end, so you’d return 2.

Given a string that consists of brackets, write a function bracketMatch that takes a bracket string as an input and returns the minimum number of brackets you’d need to add to the input in order to make it correctly matched.

Explain the correctness of your code, and analyze its time and space complexities.

Examples:

input: text = “(()” output: 1

input: text = “(())” output: 0

input: text = “())(” output: 2 Constraints:

[time limit] 5000ms

[input] string text

1 ≤ text.length ≤ 5000 [output] integer

def bracket_match(text):
diffCounter = 0
length = len(text)

for i in range(length):
if text[i] == '(':
diffCounter += 1
elif text[i] == ')':
diffCounter -= 1
if diffCounter < 0:
diffCounter += 1

text1=")))("
print(bracket_match(text1))


Doesn't look like you've done this:

Explain the correctness of your code, and analyze its time and space complexities.

This is an anti-pattern:

    length = len(text)

for i in range(length):
# code using only text[i], but never using i


You are computing the length of text, then using a for loop of over the range(length), assigning the index to i, but then never using i for anything other than fetching the character text[i].

Far, far better is looping over the letters of text:

    for ch in text:
# use ch here.


Efficiency:

        if text[i] == '(':
# ...
elif text[i] == ')':
diffCounter -= 1
if diffCounter < 0:
diffCounter += 1
# ...


Will diffCounter ever be negative, without first subtracting 1 from it? No? Perhaps the next test belongs in the elif clause:

        if text[i] == '(':
# ...
elif text[i] == ')':
diffCounter -= 1
if diffCounter < 0:
diffCounter += 1
# ...


But that is still subtracting 1 and then (possibly) immediately adding 1 again. Better: check for the underflow condition first.

        if text[i] == '(':
# ...
elif text[i] == ')':
if diffCounter > 0:
diffCounter -= 1
else:
# ...


While the diffCounter is an understandable variable name (barely), the variable named answer is completely mysterious. Answer to what? Why is it incremented when there is an underflow? Why is it added to diffCounter at the end. Not a comment in sight, and the code is anything but self documenting.

Follow PEP-8 coding standards, and use pylint or other style checker. For instance, variables should not be camelCase, and answer +=1 needs an extra space.

• Just for the fun of it, I've refactored your suggestions, and renamed some variables into this repl. Feb 10, 2019 at 1:21
• @holroy I disagree with your space complexity. While it is true the input string has N characters, you are only using 2 extra scalar state variables, so I'd say the space complexity is $O(1)$. Feb 10, 2019 at 5:58

From my experience in job interviews that question usually takes you to implements a solution with one type of data-structure.

A good implementation will be using a stack that load each '(' bracket and unloads each ')' bracket. In that way you can iterate over the text and if you encounter ') bracket beforehand you add to the result.

In Python you can use list type object as a Stack, reference.

Implementation example using stack in python3:

def bracket_match(text):
pairs = {'(': ')'}  # Using dictionary for O1 get
sk = []
res = 0
for c in text:
if c in pairs:
sk.append(pairs[c])
elif sk and c == sk[-1]:
sk.pop()
else:
res += 1
return res + len(sk)

• Forgot to return the len of the stack obviously, thanks! Feb 9, 2019 at 16:25
• a big -1 from me. 1) This is a code review. you should review the code of the OP and not present your solutions of the problem. If you have your implemented a solution and want to know what this community thinks about your solution then post your solution as question and it will be reviewed.2) it makes no sens to use a stack if an integer variable is sufficient, 3)your code isn't good and the OP should not try to copy it. Feb 10, 2019 at 8:10
• apparently you copied most part of your code from here. But the original code handles different types of brackets and this makes it necessary to use a stack. In the OP there is only one kind of brackets is used and a stack makes no sense. Also the usage of the dictionary 'pair' makes sense in the original source but no sense in your code. It does not make sense to present code here that was written by other people that you apparently do not completely understand ... Feb 10, 2019 at 8:52
• ... and I think it is very impolite to use code of other people without citing the source. Feb 10, 2019 at 8:54
• @hodisr, Your suggestion to start with a stack is a good one, but if you can get rid of the stack and reduce the space complexity (without sacrificing the time complexity), you should at least make that suggestion to your interviewer during your coding interview and ask if they would prefer that solution (to which, they'll probably say 'yes'). And no, those problems you saw on leetcode and hackerrank may all look identical to this one, but they're not completely identical. And if you want to do well during your technical coding interviews, you need to be able to pick up on those differences. May 7, 2021 at 0:56