# [Python] is this a cheating method? accepted with 40ms, easy to understand, but

• ``````class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
n = len(s)
if n == 0:
return True

if n % 2 != 0:
return False

while '()' in s or '{}' in s or '[]' in s:
s = s.replace('{}','').replace('()','').replace('[]','')

if s == '':
return True
else:
return False``````

• Brilliant solution.

• But what? It is good solution.

• @Windy-Ground because of the induction of replace, this might not be O(n)

• @wuyi365 The running time for this solution is O(N^2).
Consider this case where the s = {{{}}}
Replace function will replace only one set {} at a time. Replace itself takes O(N) time because it will have to search the entire string. On top of this, we have while loop which runs for O(N/2) times.

So O(N) * O(N/2) results in O(N^2)

• Although time consuming, but the idea is very leet : )

• So Brilliant!

• instead of last if-else you can simply write `return s == ''`

• it's brilliant,i learned so much

• Cannot believe my eye when i first saw this idea,so easy to understand!!!

• Smart idea.

Could be shortened to:

``````        while "()" in s or "{}" in s or "[]" in s:
s = s.replace("()","").replace("{}","").replace("[]","")
return len(s) == 0

``````

It sacrifices speed somewhat though.

• For the last part:

``````return bool(s)
``````

• cool!!!!!!!!!!!

• Very brilliant solution.

• A good solution!!!!

• @acheiver Thanks, your analysis is very impressive, I agree with you, it's not a normal solution.

: )

• @wuyi365 awesome....

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