Python solution using stack operation


  • 0
    H

    The idea is to use stack operation to do the match. Traverse the string from left to right: if a left half parenthesis encountered, we push its right half to the stack; if a right half encountered, we compare it with stack top (they should be the same. Otherwise, the string is not valid) and pop the stack. After the traverse, the stack should be null (otherwise the string is not valid).

    class Solution(object):
        def isValid(self, s):
            """
            :type s: str
            :rtype: bool
            """
            n = len(s)
            
            D_match = {'(':')', '[':']', '{':'}'}
            D_left = {'(':True, '[':True, '{':True, ')':False, ']':False, '}':False}
            stack = []
            for i in range(n):
                if D_left[s[i]]==True:  # if current char is a left half, append its right half to stack
                    stack.append(D_match[s[i]])
                else:   # if current char is a right half, compare it with stack top
                    if len(stack) > 0 and stack[-1] == s[i]:
                        stack.pop()
                    else:
                        return False
            if len(stack) == 0:
                return True
            else:
                return False
    

Log in to reply
 

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