Valid Parentheses

Question

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Tags

• String
• Stack

Thought

Use the stack to store and pop.

Code

class Solution(object):
    def isValid(self, s):
        """
        Use stack
        :type s: str
        :rtype: bool
        """
        stack = []
        for ch in s:
            if ch in '([{':
                stack.append(ch)
            else:
                if len(stack) == 0:
                    return False
                newCh = stack.pop()
                if (ch == ')' and newCh != '(') or (ch == ']' and newCh != '[') or (ch == '}' and newCh != '{'):
                    return False
        return len(stack) == 0