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.

view plainprint?

1. class Solution:  
2.     # @param {string} s  
3.     # @return {boolean}  
4.     def isValid(self, s):  
5.         dic = {')':'(', '}':'{', ']':'['}  
6.         stack = []  
7.         for p in s:  
8.             if p not in dic:  
9.                 stack.append(p)  
10.             elif not stack or dic[p] != stack.pop(-1):  
11.                 return False  
12.         return not 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