fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
--------------
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
https://ideone.com/vaKzgX
language:
Python 3 (python  3.9.5)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!