follow-up - Checking Nested Bracket Levels in Strings Programming Challenge

Question

A follow-up to this question, this post improves on test case issues.

To restate problem parameters, a given string S is considered closed if it:

• Has a matching opening and closing bracket or no brackets at all
• Respects bracket nesting levels
• Has no more than at least one of each bracket type in it

Note that the strings can contain any characters.

Is there a way to this program more efficient?

bracket_levels.py

import re


BRACKETS = dict([
    ('(', ')'),
    ('[', ']'),
    ('{', '}'),
    ('<', '>')
])


def hasClosedBrackets(s: str) -> bool:
    L = len(s)

    if L == 0:
        return False

    if L == 1:
        return not (s in BRACKETS.keys() or s in BRACKETS.values())

    S = s[:]

    def checkSubstring(sub: str):
        for (o, c) in BRACKETS.items():
            if (o in sub and c in sub and sub.index(c) < sub.index(o)) or (sub.count(o) != sub.count(c)):
                return False

        return True

    for (o, c) in BRACKETS.items():
        pattern = r'(?<=\{}).+?(?=\{})'.format(o, c)

        for match in re.findall(pattern, S):
            S.replace(match, '')

            if not checkSubstring(match):
                return False

    return checkSubstring(S)


if __name__ == '__main__':
    tests = list(BRACKETS.keys())
    tests.extend(list(BRACKETS.values()))
    tests += [
        'a',
        '(]',
        '((((',
        '({[<',
        ')}]>({[<',
        '}{',
        '(())',
        '()[{]}',
        'abc',
        '(<[{a}s]>d)f',
        '<as>df',
        '()[{}]',
        '(){}[]'
    ]

    for test in tests:
        print(test, ':', hasClosedBrackets(test))

Output

( : False
[ : False
{ : False
< : False
) : False
] : False
} : False
> : False
a : True
(] : False
(((( : False       
({[< : False       
)}]>({[< : False   
}{ : False
(()) : False       
()[{]} : False     
abc : True
(<[{a}s]>d)f : True
<as>df : True
()[{}] : True
(){}[] : True

Answer 1

Here's one opportunity to save cycles. The patterns for the brackets are getting compiled every time hasClosedBrackets is called.

Something like this could be added right after BRACKETS is defined:

brackets_compiled = {
    (o, c): re.compile(r"(?<=\{}).+?(?=\{})".format(o, c)) for o, c in BRACKETS.items()
}

Then the following three lines can be modified:

From:

    for (o, c) in BRACKETS.items():
        pattern = r'(?<=\{}).+?(?=\{})'.format(o, c)
        for match in re.findall(pattern, S):

To:

    for (o, c), pattern in brackets_compiled.items():
        for match in pattern.findall(S):

With this, the patterns are compiled once and that can be looped through each time. This can also be changed to the following if (o, c) aren't needed:

    for pattern in brackets_compiled.values():
        for match in pattern.findall(S):