首页 > 代码库 > LintCode Python 简单级题目 423.有效的括号序列

LintCode Python 简单级题目 423.有效的括号序列

题目描述:

 

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

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

 

样例

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

 

标签 
栈 谷歌

 

题目分析:

 

循环字符串,遇左括号入栈。

遇右括号,从栈顶取元素然后配对,判断配对结果。

最后再判断栈是否不为空。

 

 

源码:

 

class Solution:
    # @param {string} s A string
    # @return {boolean} whether the string is a valid parentheses
    def isValidParentheses(self, s):
        # Write your code here
        if s is None: return False
        
        x = [‘[‘,‘(‘,‘{‘]
        y = ["]",")","}"]
        z = ["()","[]","{}"]
        
        res = []
        for i in s:
            if i in x:
                res.append(i) # 入栈
            elif i in y:
                # 如果收到一个右括号,但是res中无左括号,直接返回False
                if res == []:
                    return False
                else:
                    temp = res.pop(-1) + i
                    # 其余情况,出栈一个左括号,判断左括号+右括号是否有效
                    if temp not in z:
                        return False
        # 如果所有括号对都满足,但是res还有左括号,返回False
        if len(res) != 0:
            return False
        return True

 

  

 

LintCode Python 简单级题目 423.有效的括号序列