Leetcode 棧 Valid Parentheses

Leetcode 棧 Valid Parentheses

Valid Parentheses

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.

題意：有三對括號'('和')'，'['和']'，'{'和'}'，判斷給定的括號字符串是否匹配

思路：用棧

1.遇到左括號就壓棧

2.遇到右括號就判斷棧頂的括號和當前的括號是否是一對，如果棧為空或不匹配，說明整個字符串的括號不匹配，如果匹配，則將棧頂括號出棧

3.如果最終棧中的元素為0，則說明字符串匹配，否則不匹配

復雜度：時間O(n)，空間O(n)

class Solution:
# @return a boolean
def isValid(self, s):
if s == '': return True
stack = []
left = '([{';right = ')]}'
for c in s:
if c == '(' or c == '[' or c =='{':
stack.append(c); continue
for i in xrange(3):
if c == right[i]:
if not stack or stack[-1] != left[i]:
return False
else:
stack.pop(); continue
return not stack