Easy Python Solution, O(1) space


  • 6
    G
    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
    

  • 2
    C

    @greg-irl honestly this is beautiful


  • 0
    H

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


  • 0
    Y

    whats x? in the while loop


  • 1
    S

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


  • 0
    G

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


  • 1
    A

    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.


  • 0
    X

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


  • 0
    P

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


Log in to reply
 

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