【LeetCode】（No.020）有效的括号

点击上方“Ahab杂货铺”，选择“置顶公众号”

技术分享第一时间送达！

---

NO.20 有效的括号

一、写在前面

刷题模块的初衷是恶补数据结构和算法，不管自己的公众号怎样变化，刷题这个模块一定会保留下去，期待自己能成为offer收割机。

LeetCode 第十九题传输门：【LeetCode】（No.019）删除链表的倒数第N个节点 今天给大家分享的是LeetCode 第二十题：有效的括号。前十题汇总：【LeetCode】打卡记录（NO.1-10）。

为面试而生，期待你的加入。

二、今日题目

给定一个只包括

'('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 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 == ''

【推荐阅读】

欢迎您的点赞和分享

▲长按关注此公众号