Valid Parentheses

Problem Description

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.

Solution

This is an easy solution using stack.

class Solution:
    # @param {string} s
    # @return {boolean}
    def isValid(self, s):
        dic = {')':'(', '}':'{', ']':'['}
        stack = []
        for p in s:
            if p not in dic:
                stack.append(p)
            elif not stack or dic[p] != stack.pop(-1):
                return False
        return not stack