fork download
  1. def isValid(s: str) -> bool:
  2. if len(s) % 2 != 0:
  3. return False
  4.  
  5. for i in range(len(s) // 2):
  6. s = s.replace("()", "").replace("[]", "").replace("{}", "")
  7.  
  8. return len(s) == 0
  9.  
  10.  
  11. def is_balanced(s, brackets={ '(': ')', '[': ']', '{': '}' }):
  12. if len(s) % 2 != 0:
  13. return False
  14. open_brackets = set(brackets.keys())
  15. close_brackets = set(brackets.values())
  16. stack = []
  17. for c in s:
  18. if c in open_brackets:
  19. stack.append(c)
  20. elif c in close_brackets:
  21. # close bracket without respective opening, string is invalid
  22. if len(stack) == 0:
  23. return False
  24. # close bracket doesn't correspond to last open bracket, string is invalid
  25. if c != brackets[stack[-1]]:
  26. return False
  27. stack.pop()
  28. else: # invalid char
  29. return False
  30.  
  31. return len(stack) == 0
  32.  
  33.  
  34. def test(func):
  35. for s in ['()', '{[(())]{()[()]}}' * 1000, ('{[(())]{()[()]}}' * 1000) + '{', ')(', '())', '[}', '()[[]{}', '(ab)']:
  36. func(s)
  37.  
  38.  
  39.  
  40. from timeit import timeit
  41.  
  42. # run 10 times each test
  43. params = { 'number' : 10, 'globals': globals() }
  44.  
  45. s = '{[(())]{()[()]}}' * 500
  46. s += '))'
  47. s += '{[(())]{()[()]}}' * 500
  48. print('--------------\nUnbalanced in the middle')
  49. print(timeit('isValid(s)', **params))
  50. print(timeit('is_balanced(s)', **params))
  51.  
  52. s = '))'
  53. s += '{[(())]{()[()]}}' * 500
  54. s += '{[(())]{()[()]}}' * 500
  55. print('--------------\nUnbalanced in the beginning')
  56. print(timeit('isValid(s)', **params))
  57. print(timeit('is_balanced(s)', **params))
  58.  
  59. s = '{[(())]{()[()]}}' * 1000
  60. s += '))'
  61. print('--------------\nUnbalanced in the end')
  62. print(timeit('isValid(s)', **params))
  63. print(timeit('is_balanced(s)', **params))
  64.  
  65. s = '{[(())]{()[()]}}' * 1000
  66. print('--------------\nBalanced')
  67. print(timeit('isValid(s)', **params))
  68. print(timeit('is_balanced(s)', **params))
  69.  
  70. # used smaller size due to time limit
  71. s = '{[((ab))]{()[()]}}' * 500
  72. print('--------------\nUnbalanced with invalid chars')
  73. print(timeit('isValid(s)', **params))
  74. print(timeit('is_balanced(s)', **params))
  75.  
Success #stdin #stdout 0.57s 9696KB
stdin
Standard input is empty
stdout
--------------
Unbalanced in the middle
0.01996097806841135
0.009705492295324802
--------------
Unbalanced in the beginning
0.02055668644607067
1.0680407285690308e-05
--------------
Unbalanced in the end
0.02053823322057724
0.01913260016590357
--------------
Balanced
0.019231285899877548
0.019136781804263592
--------------
Unbalanced with invalid chars
0.41696662548929453
1.7000362277030945e-05