相关代码已经上传到github:https://github.com/exploitht/leetcode-python
文中代码为了不动官网提供的初始几行代码内容,有一些不规范的地方,比如函数名大小写问题等等;更合理的代码实现参考我的github repo
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、解题
这道题比较简单,上面读题已经讲到用栈来实现,代码逻辑很简单,如下:
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
# 循环读取字符串s,如果是左括号则进栈,如果是有括号则出栈
# 出栈的时候栈不能为空,循环结束的时候栈需要为空
pars = {'(': 1, '[': 2, '{': 3, ')': -1, ']': -2, '}': -3}
stack = list()
for par in s:
if pars.get(par) > 0:
stack.append(par)
else:
if len(stack) > 0:
if pars.get(stack.pop()) == abs(pars.get(par)):
continue
else:
return False
else:
return False
return True if len(stack) == 0 else False