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.
?
Trick:?
?
Data structure: stack. LIFO (Last in first out)
?
复制代码
class Solution:
? ? # @return a boolean
? ? def isValid(self, s):
? ? ? ? stack = []
? ? ? ? left, right = '([{', ')]}'
? ? ? ? for i in s:
? ? ? ? ? ? if i in left:
? ? ? ? ? ? ? ? stack.append(i); continue
? ? ? ? ? ? for j in range(3):
? ? ? ? ? ? ? ? if right[j] == i:
? ? ? ? ? ? ? ? ? ? if not stack or stack[-1] != left[j]:
? ? ? ? ? ? ? ? ? ? ? ? return False
? ? ? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? stack.pop()
? ? ? ? ? ? ? ? ? ? ? ? continue
? ? ? ? return not stack