【LeetCode】（No.020）有效的括号
NO.20 有效的括号
一、写在前面
刷题模块的初衷是恶补数据结构和算法，不管自己的公众号怎样变化，刷题这个模块一定会保留下去，期待自己能成为offer收割机。
LeetCode 第十九题传输门：【LeetCode】（No.019）删除链表的倒数第N个节点 今天给大家分享的是LeetCode 第二十题：有效的括号。前十题汇总：【LeetCode】打卡记录（NO.1-10）。
为面试而生，期待你的加入。
二、今日题目
给定一个只包括
'('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true示例 2:
输入: "()[]{}"
输出: true示例 3:
输入: "(]"
输出: false示例 4:
输入: "([)]"
输出: false示例 5:
输入: "{[]}"
输出: true三、 分析
数据结构中有一个栈的概念，解题思路一就是利用栈的思路解决问题，遇到左括号就进栈，遇到右括号，就判断栈顶元素是否与之匹配，匹配的话就pop出栈，不匹配的话就返回false。
第二种解题思路是小詹提供的，利用python种的replace函数将成对的可匹配括号用空字符代替 ，之后依次进行 ，若是有效的括号 ，必然经过有限次循环后 ，字符串为空 ，则最后判断字符串是否为空即可。真的非常的巧妙利用python语言特性就可以将题目解决。
四、解题
第一种解题：
1class Solution(object):
2 def isValid(self, s):
3 """
4 :type s: str
5 :rtype: bool
6 """
7 stack = collections.deque()
8 for i in s:
9 if i in {'(','{','['}:
10 stack.append(i)
11 if i in {')','}',']'}:
12 if len(stack)!=0:
13 tmp = stack.pop()
14 else:
15 return False #检查栈是否为空
16 if tmp=='(' and i!=')':
17 return False
18 elif tmp=='{' and i!='}':
19 return False
20 elif tmp=='[' and i!=']':
21 return False
22 else:
23 pass
24 return len(stack) == 0 #如果都匹配是不可能有剩下的第二种解题：
1class Solution:
2 def isValid(self, s):
3 """
4 :type s: str
5 :rtype: bool
6 """
7 n = len(s)
8 # 空字符串 ，即无括号，但是也是有效的
9 if n == 0:
10 return True
11 # 字符串长度为奇数 ，不可能匹配
12 if n % 2 != 0:
13 return False
14 #算是做了个一个弊 ，利用python的replace剔除成对的括号
15 while '()' in s or '{}' in s or '[]' in s:
16 s = s.replace('{}','').replace('()','').replace('[]','')
17
18 return s == ''本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-11-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录