Valid Parentheses [LeetCode 20]

1- 问题描述

　　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.

2- 思路分析^[1]

　　利用一个栈来保存前括号，然后有后括号来时弹出栈顶来判断。

3- Python实现

 1 class Solution:
 2     # @param {string} s
 3     # @return {boolean}
 4     def isValid(self, s):
 5         if not s: return False
 6         l = len(s)
 7         if l % 2 == 1: return False    # 长度为奇数返回False
 8         bracket = {'(':')', '[':']', '{':'}'}
 9         stack = []    # 栈保存前括号
10         for i in range(l):
11             if s[i] in bra:
12                 stack.append(s[i])    # 前括号则入栈
13             else:
14                 try:
15                     top = stack.pop()
16                 except:
17                     return False    # 取不出前括号返回False
18                 if bracket[top] != s[i]:    # 比较是否与出栈前括号匹配
19                     return False
20         if not len(stack): return True    # 遍历完若栈为空，则完全匹配
21         return False    # 栈内还有元素，则不匹配

[1] [LeetCode] Valid Parentheses