simple python with stack and explanation


  • 0
    R

    1). make a dictionary to record all valid parenthesis pair.
    2). loop over the string, append every 'first half of parenthesis' to a stack.
    3). And every time we meet the second half of any parenthesis, pop the the stack and compare. If they are not equal, return false.
    4). If the stack still has element after loop. return false other wise true.

    DICT = {'(':')','{':'}','[':']'}
    
    def isValid(s):
        s_len = len(s)
        first_partial_half = []
        for i in range(s_len):
            if s[i] not in DICT.values():
                first_partial_half.append(s[i])
            else:
                # start pop
                if not first_partial_half or (s[i]!=DICT[first_partial_half.pop()]):
                    return False
        if first_partial_half:
            return False
        return True
    

Log in to reply
 

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