Python Solution using Stack


  • 1
    L

    '''
    def isValid(s):

    # When len(s) is odd number, bracket pair doesn't match, invalid
    if len(s) % 2 == 1:
        return False
    
    OPEN_BRACKET = {"(":0, "[":0, "{":0}
    CLOSE_BRACKET = {")":0, "]":0, "}":0}
    PAIR = {")":"(", "]":"[", "}":"{"}
    
    # Stack stores open brackets only
    stack = []
    
    # A string intput that starts with close bracket is invalid
    if s[0] in CLOSE_BRACKET:                          # O(1) 
        return False
    else:
        stack.append(s[0])                             # O(1)
        
        
    for idx in range(1, len(s)):                       # O(N)
        # If a char is open bracket, add to stack
        if s[idx] in OPEN_BRACKET:                     # O(1)
            stack.append(s[idx])                       # O(1)
        # If a char is close bracket, 
        # pop the open bracket on the top of stack, 
        # and then compare whether that is right pair
        elif s[idx] in CLOSE_BRACKET:
            if stack.pop() != PAIR[s[idx]]:            # O(1)
                return False
    
    # If iteration ended wo/ poping out all elements from Stack means 
    # there were only open brackets in input string
    if len(stack) != 0:
        return False
    else: 
        return True
    

    '''


Log in to reply
 

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