def isValid( s: str ) -> bool :
if len ( s) % 2 != 0 :
return False
for i in range ( len ( s) // 2 ) :
s = s.replace ( "()" , "" ) .replace ( "[]" , "" ) .replace ( "{}" , "" )
return len ( s) == 0
def is_balanced( s, brackets= { '(' : ')' , '[' : ']' , '{' : '}' } ) :
if len ( s) % 2 != 0 :
return False
open_brackets = set ( brackets.keys ( ) )
close_brackets = set ( brackets.values ( ) )
stack = [ ]
for c in s:
if c in open_brackets:
stack.append ( c)
elif c in close_brackets:
# close bracket without respective opening, string is invalid
if len ( stack) == 0 :
return False
# close bracket doesn't correspond to last open bracket, string is invalid
if c != brackets[ stack[ -1 ] ] :
return False
stack.pop ( )
else : # invalid char
return False
return len ( stack) == 0
def test ( func) :
for s in [ '()' , '{[(())]{()[()]}}' * 1000 , ( '{[(())]{()[()]}}' * 1000 ) + '{' , ')(' , '())' , '[}' , '()[[]{}' , '(ab)' ] :
func( s)
from timeit import timeit
# run 10 times each test
params = { 'number' : 10 , 'globals' : globals ( ) }
s = '{[(())]{()[()]}}' * 500
s += '))'
s += '{[(())]{()[()]}}' * 500
print ( '--------------\n Unbalanced in the middle' )
print ( timeit ( 'isValid(s)' , **params) )
print ( timeit ( 'is_balanced(s)' , **params) )
s = '))'
s += '{[(())]{()[()]}}' * 500
s += '{[(())]{()[()]}}' * 500
print ( '--------------\n Unbalanced in the beginning' )
print ( timeit ( 'isValid(s)' , **params) )
print ( timeit ( 'is_balanced(s)' , **params) )
s = '{[(())]{()[()]}}' * 1000
s += '))'
print ( '--------------\n Unbalanced in the end' )
print ( timeit ( 'isValid(s)' , **params) )
print ( timeit ( 'is_balanced(s)' , **params) )
s = '{[(())]{()[()]}}' * 1000
print ( '--------------\n Balanced' )
print ( timeit ( 'isValid(s)' , **params) )
print ( timeit ( 'is_balanced(s)' , **params) )
# used smaller size due to time limit
s = '{[((ab))]{()[()]}}' * 500
print ( '--------------\n Unbalanced with invalid chars' )
print ( timeit ( 'isValid(s)' , **params) )
print ( timeit ( 'is_balanced(s)' , **params) )
ZGVmIGlzVmFsaWQoczogc3RyKSAtPiBib29sOgogICAgaWYgbGVuKHMpICUgMiAhPSAwOgogICAgICAgIHJldHVybiBGYWxzZQoKICAgIGZvciBpIGluIHJhbmdlKGxlbihzKSAvLyAyKToKICAgICAgICBzID0gcy5yZXBsYWNlKCIoKSIsICIiKS5yZXBsYWNlKCJbXSIsICIiKS5yZXBsYWNlKCJ7fSIsICIiKQoKICAgIHJldHVybiBsZW4ocykgPT0gMAoKCmRlZiBpc19iYWxhbmNlZChzLCBicmFja2V0cz17ICcoJzogJyknLCAnWyc6ICddJywgJ3snOiAnfScgfSk6CiAgICBpZiBsZW4ocykgJSAyICE9IDA6CiAgICAgICAgcmV0dXJuIEZhbHNlCiAgICBvcGVuX2JyYWNrZXRzID0gc2V0KGJyYWNrZXRzLmtleXMoKSkKICAgIGNsb3NlX2JyYWNrZXRzID0gc2V0KGJyYWNrZXRzLnZhbHVlcygpKQogICAgc3RhY2sgPSBbXQogICAgZm9yIGMgaW4gczoKICAgICAgICBpZiBjIGluIG9wZW5fYnJhY2tldHM6CiAgICAgICAgICAgIHN0YWNrLmFwcGVuZChjKQogICAgICAgIGVsaWYgYyBpbiBjbG9zZV9icmFja2V0czoKICAgICAgICAgICAgIyBjbG9zZSBicmFja2V0IHdpdGhvdXQgcmVzcGVjdGl2ZSBvcGVuaW5nLCBzdHJpbmcgaXMgaW52YWxpZAogICAgICAgICAgICBpZiBsZW4oc3RhY2spID09IDA6CiAgICAgICAgICAgICAgICByZXR1cm4gRmFsc2UKICAgICAgICAgICAgIyBjbG9zZSBicmFja2V0IGRvZXNuJ3QgY29ycmVzcG9uZCB0byBsYXN0IG9wZW4gYnJhY2tldCwgc3RyaW5nIGlzIGludmFsaWQKICAgICAgICAgICAgaWYgYyAhPSBicmFja2V0c1tzdGFja1stMV1dOgogICAgICAgICAgICAgICAgcmV0dXJuIEZhbHNlCiAgICAgICAgICAgIHN0YWNrLnBvcCgpCiAgICAgICAgZWxzZTogIyBpbnZhbGlkIGNoYXIKICAgICAgICAgICAgcmV0dXJuIEZhbHNlCgogICAgcmV0dXJuIGxlbihzdGFjaykgPT0gMAoKCmRlZiB0ZXN0KGZ1bmMpOgogICAgZm9yIHMgaW4gWycoKScsICd7WygoKSldeygpWygpXX19JyAqIDEwMDAsICgne1soKCkpXXsoKVsoKV19fScgKiAxMDAwKSArICd7JywgJykoJywgJygpKScsICdbfScsICcoKVtbXXt9JywgJyhhYiknXToKICAgICAgICBmdW5jKHMpCgoKCmZyb20gdGltZWl0IGltcG9ydCB0aW1laXQKCiMgcnVuIDEwIHRpbWVzIGVhY2ggdGVzdApwYXJhbXMgPSB7ICdudW1iZXInIDogMTAsICdnbG9iYWxzJzogZ2xvYmFscygpIH0KCnMgPSAne1soKCkpXXsoKVsoKV19fScgKiA1MDAKcyArPSAnKSknCnMgKz0gJ3tbKCgpKV17KClbKCldfX0nICogNTAwCnByaW50KCctLS0tLS0tLS0tLS0tLVxuVW5iYWxhbmNlZCBpbiB0aGUgbWlkZGxlJykKcHJpbnQodGltZWl0KCdpc1ZhbGlkKHMpJywgKipwYXJhbXMpKQpwcmludCh0aW1laXQoJ2lzX2JhbGFuY2VkKHMpJywgKipwYXJhbXMpKQoKcyA9ICcpKScKcyArPSAne1soKCkpXXsoKVsoKV19fScgKiA1MDAKcyArPSAne1soKCkpXXsoKVsoKV19fScgKiA1MDAKcHJpbnQoJy0tLS0tLS0tLS0tLS0tXG5VbmJhbGFuY2VkIGluIHRoZSBiZWdpbm5pbmcnKQpwcmludCh0aW1laXQoJ2lzVmFsaWQocyknLCAqKnBhcmFtcykpCnByaW50KHRpbWVpdCgnaXNfYmFsYW5jZWQocyknLCAqKnBhcmFtcykpCgpzID0gJ3tbKCgpKV17KClbKCldfX0nICogMTAwMApzICs9ICcpKScKcHJpbnQoJy0tLS0tLS0tLS0tLS0tXG5VbmJhbGFuY2VkIGluIHRoZSBlbmQnKQpwcmludCh0aW1laXQoJ2lzVmFsaWQocyknLCAqKnBhcmFtcykpCnByaW50KHRpbWVpdCgnaXNfYmFsYW5jZWQocyknLCAqKnBhcmFtcykpCgpzID0gJ3tbKCgpKV17KClbKCldfX0nICogMTAwMApwcmludCgnLS0tLS0tLS0tLS0tLS1cbkJhbGFuY2VkJykKcHJpbnQodGltZWl0KCdpc1ZhbGlkKHMpJywgKipwYXJhbXMpKQpwcmludCh0aW1laXQoJ2lzX2JhbGFuY2VkKHMpJywgKipwYXJhbXMpKQoKIyB1c2VkIHNtYWxsZXIgc2l6ZSBkdWUgdG8gdGltZSBsaW1pdApzID0gJ3tbKChhYikpXXsoKVsoKV19fScgKiA1MDAKcHJpbnQoJy0tLS0tLS0tLS0tLS0tXG5VbmJhbGFuY2VkIHdpdGggaW52YWxpZCBjaGFycycpCnByaW50KHRpbWVpdCgnaXNWYWxpZChzKScsICoqcGFyYW1zKSkKcHJpbnQodGltZWl0KCdpc19iYWxhbmNlZChzKScsICoqcGFyYW1zKSkK