【边学边敲边记】LeetCode008:有效的括号
一、写在前面
LeetCode 第七题 最接近的三数之和 传输门:LeetCode007 : 最接近的三数之和
今天给大家分享的是LeetCode 数组与字符串 第八题:有效的括号,为面试而生,期待你的加入。
二、今日题目
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
三、 分析
在《算法面试40讲》里有讲到这个题目,当时听老师讲的时候我想到我大二学《数据结构》时的一个题目:求一个表达式的值(比如:5*(3+2) ),当时用c语言做这个题花了两节课,计算表达式这个题比较麻烦的主要是运算优先级的判断,相比之下,只用判断括号是否有效(即匹配),就太小case了~思路分析如下:
四、解题
我的方法:
# 我的方法
class Solution:
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
reg_dict = {')':'(','}':'{',']':'['}
# 括号匹配集
temp_list = []
# 临时存储栈
for i in range(len(s)):
if s[0] in reg_dict:
return False
if s[i] not in reg_dict: # 左括号,入栈
temp_list.append(s[i])
else: # 右括号,取出栈顶,匹配
if temp_list == []: # 有右括号无左括号可匹配
return False
if not temp_list[-1] == reg_dict[s[i]]: # 左右括号不匹配
return False
temp_list.pop() # 匹配成功出栈
if temp_list != []:
return False
return True
提交结果
测试数据:76组
运行时间:20ms
击败人百分比:100%
五、疑惑
值得一说的是,我最开始区分字符是左括号还是有括号用的是列表,然后运行结果在76.53%,也是做第一题两数之和的经验,然后选择了直接用字典,果然速度快多了,飙升到100%,这块,大家以后也可以多注意,一个小细节,改变你的命运,这也是老表的第一个100%,今天好好纪念一下。
六、结语
好的,最后再说两句,刷LeetCode已经一个多月了,虽然只刷了8题,但我觉得,我还是用心了的,同时也学到了很多东西。
现在带着读者刷LeetCode的公众号很多,我不敢说我是最厉害的,我只能说我能做到最用心,在题目分析、解题思路、最优解寻找中,而不是仅仅发一个能解出题目的代码,代码是死的,人是活的,思想是活的,我会继续坚持,一周最少两题。
另外,刷第一题就说了,坚持一个月后会建一个LeetCode算法刷题交流群,群其实找就建了,只是最开始为了方便管理和学习交流,只拉了几个研究生学长学姐,现在一个多月了,效果还不错,所以现在算法学习交流群面向所有读者开放,加我微信:zs820553471,备注:LeetCode 即可。
坚持 and 努力 : 终有所获。