有效的括号序列——算法面试刷题4（for google），考察stack

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了有效的括号序列——算法面试刷题4（for google），考察stack，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1209字，纯文字阅读大概需要2分钟。

内容图文

给定一个字符串所表示的括号序列，包含以下字符： '(', ')', '{', '}', '[' and ']'， 判定是否是有效的括号序列。

括号必须依照 "()" 顺序表示， "()[]{}" 是有效的括号，但 "([)]" 则是无效的括号。

您在真实的面试中是否遇到过这个题？??

样例

样例 1：

输入："([)]"
输出：False

样例 2：

输入："()[]{}"
输出：True

挑战

O(n)的时间，n 为括号的个数。

我的代码：

class Solution:
    """
    @param s: A string
    @return: whether the string is a valid parentheses
    """
    def isValidParentheses(self, s):
        # write your code here
        match_par = {"(": ")", "[": "]", "{": "}"}
        l_par = set(match_par.keys())
        r_par = set(match_par.values())
        stack = []
        for c in s:
            if c in l_par:
                stack.append(c)
            elif c in r_par:
                if not stack or match_par[stack.pop()] != c:
                    return False
            else:
                pass
        return len(stack) == 0

 参考代码：

class Solution(object):
    '''
    题意：输入一个只包含括号的字符串，判断括号是否匹配
    模拟堆栈，读到左括号压栈，读到右括号判断栈顶括号是否匹配
    '''
    def isValidParentheses(self, s):
        stack = []
        for ch in s:
            # 压栈
            if ch == '{' or ch == '[' or ch == '(':
                stack.append(ch)
            else:
                # 栈需非空
                if not stack:
                    return False
                # 判断栈顶是否匹配
                if ch == ']' and stack[-1] != '[' or ch == ')' and stack[-1] != '(' or ch == '}' and stack[-1] != '{':
                    return False
                # 弹栈
                stack.pop()
        return not stack

 值得学习的地方：

return not stack

内容总结

以上是互联网集市为您收集整理的有效的括号序列——算法面试刷题4（for google），考察stack全部内容，希望文章能够帮你解决有效的括号序列——算法面试刷题4（for google），考察stack所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---