[数据结构与算法]有效的括号

Leetcode地址：20. 有效的括号 - 力扣（LeetCode） (leetcode-cn.com)

考察知识点：Stack

python没有直接的内置栈，可以当成栈用的有：

1. 列表
2. collections.deque
3. queue.LifoQueue

Python 栈（后进先出）|极客教程 (geek-docs.com)

这里使用内置的list来实现Stack已足够

解题思路：

1.遇到左括号进栈，遇到右括号，出栈，检查是否匹配。否，则返回false

2.遍历完字符串后，栈为空，则是“有效括号”；否则，返回false

我的解题code:

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack=list()
        for a in s:
            if a in ['(','[','{']:
                stack.append(a)
            elif stack:
                b=stack.pop()
                if a==')' and b=='(':
                    continue
                elif a==']' and b=='[':
                    continue
                elif a=='}' and b=='{':
                    continue
                else:
                    return False
            else:
                return False
        if stack==[]:
            return True
        else:
            return False

时间复杂度：O(n)

空间复杂度：O(n)

简洁代码：

def isValid(self, s):
    """
    :type s: str
    :rtype: bool
    """
    stack=list()
    paren_map={')':'(',']':'[','}':'{'}
    for a in s:
        if a not in paren_map.keys():
            stack.append(a)
        elif not stack or paren_map[a]!=stack.pop():
            return False
    return not stack

08 | 面试题：判断括号字符串是否有效 (geekbang.org)

?题解中的replace解法，时间复杂度：O(n^2/2)