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
[Python] is this a cheating method? accepted with 40ms, easy to understand, but


@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)

@wuyi365 said in [Python] is this a cheating method? accepted with 40ms, easy to understand, but:
replace
cool

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