8 line solution in python

• ``````class Solution:
def isValid(self, s):
if len(s)%2==1:
return False
else:
while ('()' in s) or ('[]' in s) or ('{}' in s):
s = s.replace('()','').replace('[]','').replace('{}','')
return (s=='')
``````

• This solution is so clean and amazing! I love this solution!

• if '([{}])' ?

• @Zoulfwin86 this still works, cause there is always at least on pair of '()' '[]' '{}' in the string if the string is valid. it will remove '()' '[]' '{}' from inside to outside.

• I think you can remove the else as well to save a line.

• Although this solution is condensed, it is a very slow algorithm with a time complexity of O(n^2).

• @ShonSanchez how did you get O(n^2)?

• @heretoinfinity
Python's replace function takes O(n) time to execute since it creates a copy of the string and returns it.

In a valid string of parenthesis there are n/2 valid open/close parenthesis pairs. (e.g "({})" has "{}" "()" or "(())" has an inner "()" and an outer "()" )

So the replace function is called at least n/2 times which results in a n*(n/2) complexity which is O((n^2)/2) but in Asymptotic Complexity we ignore coefficients leaving us with a O(n^2) time complexity.

• @ShonSanchez What about the first O(n)? Does it come from the while loop?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.