首页 > 代码库 > Leetcode 栈 Valid Parentheses
Leetcode 栈 Valid Parentheses
Valid Parentheses
Total Accepted: 17916 Total Submissions: 63131My SubmissionsGiven 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
Leetcode 栈 Valid Parentheses