Welcome to Software Development on Codidact!
Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.
Comments on Detecting balanced parentheses in Python
Parent
Detecting balanced parentheses in Python
The problem
Given a string s containing just the characters
'(',')','{','}','['and']', determine if the input string is valid.An input string is valid if:
- Open brackets are closed by the same type of brackets.
- Open brackets are closed in the correct order.
The solution
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
My approach to the problem is replacing the pairs. The string is balanced if the string is empty after replacing len(str) // 2 times. Is this a good approach? How can I improve my algorithm?
Use a stack while just scanning your string once from left to right. No need for multiple (performance-wise) expensive s …
5y ago
> Is this a good approach? How can I improve my algorithm? Your code is correct and simple. That is good, and it may …
2y ago
Instead of replacing the brackets, you could do just one loop, and keep a stack with the opening brackets. Every time yo …
5y ago
You've got an inefficiency in your code, as you always do replacements 3/2 times the length of the string. That is unnec …
5y ago
Command-line timing Rather than using separate code for timing, I tried running the `timeit` module as a command-line …
2mo ago
Post
You've got an inefficiency in your code, as you always do replacements 3/2 times the length of the string. That is unnecessarily expensive.
By instead testing in each iteration whether the length actually changed, you get a much improved performance:
def is_valid(s: str) -> bool:
if len(s) % 1 != 0:
return False
# this initial value causes the loop to be skipped entirely for empty strings
prevlen = 0
# stop as soon as no further replacements have been made
while len(s) != prevlen:
prevlen = len(s)
s = s.replace("()", "").replace("[]", "").replace("{}", "")
return len(s) == 0
I've put it together with your code and hkotsubo's timing code on tio.run, and got the following:
--------------
Unbalanced in the middle
0.04957069695228711
0.002779866976197809
--------------
Unbalanced in the beginning
0.05233071401016787
0.0026999289984814823
--------------
Unbalanced in the end
0.05092682002577931
0.0026755660073831677
--------------
Balanced
0.047405752004124224
0.002398615994025022
0 comment threads