Simple Python solution, O(n) time and O(1) space


  • 0
    P
      # Number of tags must be an even number
        if len(s) % 2 != 0:
            return False
            
        stack = []
        closing_tags = {'}': '{', ']': '[', ')': '('}   # match each closing tag with its opening tag
        for tag in s:
            # If we see a closing tag, we check if the immediate opening tag matches it
            if tag in closing_tags:
                if not stack or closing_tags[tag] != stack.pop():
                    return False
            else:
                stack.append(tag)
        
        # If we still have opening tags left on stack,
        # return False
        if not stack:
            return True
        return False

Log in to reply
 

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