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 …
3y ago
Instead of replacing the brackets, you could do just one loop, and keep a stack with the opening brackets. Every time yo …
3y ago
> Is this a good approach? How can I improve my algorithm? Your code is correct and simple. That is good, and it may …
11mo ago
Command-line timing Rather than using separate code for timing, I tried running the `timeit` module as a command-line …
11mo 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 …
3y ago
Post
Is this a good approach? How can I improve my algorithm?
Your code is correct and simple. That is good, and it may be all that is needed. You have received some responses that indicate that there would be a performance problem. But, whether or not performance is an issue, and what the precise performance problem is, depends on how your code is meant to be used:
Will the code be executed frequently? Will it be executed with long input strings or with short ones? What is more likely: valid or invalid input strings? For which case do you have to give a fast answer: valid or invalid input strings? And, as the experiments from @hkotsubo show, even the expected contents of strings can play a role...
Unless that is clear, it does not make much sense to optimize the code at the cost of clarity. In your case I assume that it is an exercise from a programming lecture. Then, the code will likely be run, say, 10-100 times or so for checking your result, likely with input strings of short or moderate length. If that is true, the total execution time of all executions ever of your code (before it is being abandoned and you will look at the next exercise) will likely be below 10min. Thus, investing 11min in optimization could already be a waste of time :-).
In fact, under this assumption your code is even more complex than it needs to be: You have an initial check for odd string lengths. This check is redundant because the rest of the function works without it. The check optimizes the function's response time for some invalid cases, but at the cost of prolonging the computation for all the other cases. Thus, I recommend to get rid of the initial check to end with the most likely simplest possible solution for the problem.
Some more remarks:
-
In the explanation of the review request you gave a short summary of your approach:
My approach to the problem is replacing the pairs.
Such a short summary would would also be good as a comment in the code, maybe a bit extended as
The function analyzes the parenthesization "from inside" by iteratively deleting valid adjacent pairs of parentheses.
but given the simplicity of the code the value of such a comment may already be debatable.
-
For such a simple function, short variable names as you have chosen are fine. The name of the function fits the description of the exercise and thus may be OK in this case. Generally, for symbols to be used by the users of your code, a more descriptive name should be chosen. Again, @hkotsubo's answer is worth looking at.
-
A list of test cases would be good to have.
And, finally: It is quite possible that your instructors wanted you to learn about the use of stacks for such kinds of problems. Your solution may have come as a surprise to them. In this case, certainly, and also for the general benefit of learning new techniques I can only recommend to look at the proposals brought up by the other commenters.
0 comment threads