Solution by liav3000


  • 0
    L

    Approach #1 Use a stack [Accepted]

    Intuition

    The basic property we're testing for is that brackets are correctly nested. Brackets can nest arbitrarily deep, and in any order, but they must be symmetrically matched. Eg: [(((([{[]}]))))] This property of arbitrary nesting with symmetry can be very cleanly captured with a stack.

    Algorithm

    For each character in the string:
        if the character is an open paren: 
            put it on the stack.
        Otherwise is a close paren, so: 
            Attempt to pop off the stack.
            If the pop fails: 
                We have an unbalanced close paren, (eg: `())` therefore:
                return False
            If the char popped off the stack doesn't match the current closed paren:
                return False
    If we get to the end of the input string there are still items on the stack:
        return False, because we have unbalanced open parens (eg: `(()`.
    
    return True, because our input string has passed all our tests.
    

    Python3

    def isValid(s):
        brackets = {')': '(', '}': '{', ']': '['}
        open_brackets = brackets.values()
        stack = []
        for char in s:
            if char in open_brackets:
                stack.append(char)
            else:
                try:
                    brackets_match = brackets[char] == stack.pop()
                    if not brackets_match:
                        return False
                except IndexError:
                    return False
        if stack:
            return False
        return True
    

    Complexity Analysis
    We look at every char in the string. For every char we do a constant amount of work (either putting it on a stack O(1), or popping from the stack O(1) and comparing, O(1)). Therefore total time is O(n), where n is the length of the input string.

    • Space complexity : In the worst case half of the chars in the string get placed onto a stack. O(n/2) = O(n), therefore space is O(n).

    Pattern matching [Accepted]

    Intuition
    Another approach is to iteratively remove valid matched parens from the string. If the string is well-formed, there is always at least one innermost pair of parens. If we remove that pair of parens, there should be at least one new innermost pair of parens or the string should be empty. If we cannot remove a pair of matched parens and the string is not empty, then the string cannot be valid.

    Algorithm

    while there is a pair of matched parens in the string:
        replace that pair of parens with the empty string ''.
    If the string is the empty string return True, otherwise return False.
    

    Python3

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

    Complexity Analysis

    • Time complexity : Each check for the paren pair requires a linear scan of the input string. That means that if there are n chars in the string, we must search through it n/2 times, for a total runtime of O(n^2)

    • Space complexity: Each time we do a replace() call we need to create a new string that, in the worst case, is asymptotically n-characters long. We only need to hold a reference to one new string at a time, so space storage is O(n)


Log in to reply
 

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