有效的括号序列——算法面试刷题4(for google),考察stack

时间:2023-12-09 16:29:49

给定一个字符串所表示的括号序列,包含以下字符: '(', ')', '{', '}', '[' and ']', 判定是否是有效的括号序列。

括号必须依照 "()" 顺序表示, "()[]{}" 是有效的括号,但 "([)]" 则是无效的括号。

您在真实的面试中是否遇到过这个题?  

样例

样例 1:

输入:"([)]"
输出:False

样例 2:

输入:"()[]{}"
输出:True

挑战

O(n)的时间,n 为括号的个数。

我的代码:

class Solution:
"""
@param s: A string
@return: whether the string is a valid parentheses
"""
def isValidParentheses(self, s):
# write your code here
match_par = {"(": ")", "[": "]", "{": "}"}
l_par = set(match_par.keys())
r_par = set(match_par.values())
stack = []
for c in s:
if c in l_par:
stack.append(c)
elif c in r_par:
if not stack or match_par[stack.pop()] != c:
return False
else:
pass
return len(stack) == 0

参考代码:

class Solution(object):
'''
题意:输入一个只包含括号的字符串,判断括号是否匹配
模拟堆栈,读到左括号压栈,读到右括号判断栈顶括号是否匹配
'''
def isValidParentheses(self, s):
stack = []
for ch in s:
# 压栈
if ch == '{' or ch == '[' or ch == '(':
stack.append(ch)
else:
# 栈需非空
if not stack:
return False
# 判断栈顶是否匹配
if ch == ']' and stack[-1] != '[' or ch == ')' and stack[-1] != '(' or ch == '}' and stack[-1] != '{':
return False
# 弹栈
stack.pop()
return not stack

值得学习的地方:

return not stack