# Easy Python Solution, O(1) space

• def isValid(self, s):
delta = len(s)
while(delta != 0 and delta%2 == 0):
s = s.replace("()", "")
s = s.replace("[]", "")
s = s.replace("{}", "")
# breaks while loop if string was not altered during current pass
delta = len(s) if delta > len(s) else 0
return len(s) == 0

• @greg-irl honestly this is beautiful

• @cesarvh only when you don't care modification of original string otherwise there will be extra logic to preserve original string

• whats x? in the while loop

• @yashash it's supposed to be delta. If the string has an odd length, then the pairs are uneven.

• @hyde

def isValid(self, s):
str, delta = s, len(s)
while(delta != 0 and delta%2 == 0):
s = s.replace("()", "")
s = s.replace("[]", "")
s = s.replace("{}", "")
# breaks while loop if string was not altered during current pass
delta = len(s) if delta > len(s) else 0
return len(s) == 0, str

That wasn't a requirement in the prompt. Even so, still O(1) space, relatively minimal extra logic.

• It is a very nice idea. But every replace() would build a new string, and the longer the string, the more time it takes. So the time complexity could be O(n^2). It is not a good idea to use a lot of string operations.

• i thought about similar ideal. But the complexity should be more than O(1) i think as you probably loop more than once.

• It's not O(1) space since you're building additional strings in memory. It's not possible for this to be solved in O(1) space since matching parentheses is not a regular language (otherwise you could write a regex to do it).

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