Bracket matcher in Python

Question

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
    answer = 0
    length = len(text)

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

    return answer + diffCounter

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

Answer 1

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.

Answer 2

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)