首页 > 试题广场 >

有效括号序列

[编程题]有效括号序列

热度指数：312235 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。

数据范围：字符串长度 $0\le n \le 10000$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

"["

输出

false

示例2

输入

"[]"

输出

true

算法知识视频讲解

查看答案及解析

Python3

李昂丶

class Solution:
    def isValid(self , string: str) -> bool:
        # write code here
        class Stack:
            def __init__(self):
                self.items=[]
            def isEmpty(self):
                 return self.items == []
            def push(self,item):
                self.items.append(item)
            def pop(self):
                return self.items.pop()
            def size(self):
                return len(self.items)
        def match(open,close):
            opens='([{'
            closes=')]}'
            if opens.index(open) == closes.index(close):
                return True
            else:
                return False
        s=Stack()
        balanced=True
        index=0
        while index<len(string) and balanced:
            char=string[index]
            if char in '([{':
                s.push(char)
            else:
                if s.isEmpty():
                    balanced=False  #右括号开头，无效
                else:
                    top=s.pop()
                    if not match(top,char):
                        balanced=False
            index=index+1
        if balanced and s.isEmpty():
            return True
        else:
            return False

编辑于 2024-04-16 22:00:05 回复(0)

Python3

川流不息憨憨

class Solution:
    def isValid(self , s: str) -> bool:
        stack = []
        if len(s) % 2 != 0:
            return False
        for i in s:
            # print(stack)
            if i in ("[", '{', "("):
                stack.append(i)
                continue
            elif i in ("}", ')', "]"):
                if stack == []:
                    return False
                if i == ")" and stack.pop() == "(":
                    continue
                elif i == "}" and stack.pop() == "{":
                    continue
                elif i == "]" and stack.pop() == "[":
                    continue
                else:
                    return False
            return len(stack) == 0

编辑于 2024-03-18 20:54:34 回复(0)

Python3

牛客483061681号

class Solution:
    def isValid(self , s: str) -> bool:
        # write code here
        
        if len(s) % 2 != 0:#如果长度不是偶数，直接false
            return False
        elif s[0] == ')'&nbs***bsp;s[0] == ']'&nbs***bsp;s[0] == '}':#如果第一个元素为右括号，则false
            return False
        else:#当第一个元素是左括号,判断后续元素能否一一配对
            stack = []
            for i in s:
                if i == '('&nbs***bsp;i == '['&nbs***bsp;i == '{':#所有左括号入栈
                    stack.append(i)
                else:#当遍历到右括号时
                    if i == ')' and stack[-1]!='(':#如果列表最后一位不是能与之配对的左括号，false
                        return False
                    
                    elif i == ']' and stack[-1]!='[':
                        return False
                    
                    elif i == '}' and stack[-1]!='{':
                        return False
                    else:#是能配对的，就pop
                        stack.pop()
                 
            if stack:#如果最后列表中还有元素，则false
                return False
            else:
                return True

发表于 2024-02-20 18:53:46 回复(0)

Python3

在午休的打工人很想去夏威夷

class Solution:

def isValid(self , s: str) -> bool:

# write code here

bracket_dict = {

')': '(',

']': '[',

'}':'{'

}

stack = []

for item in s:

if item in '({[':

stack.append(item)

elif len(stack)!=0 and stack[-1] == bracket_dict.get(item):

stack.pop()

else:

return False

if len(stack) == 0:

return True

return False

编辑于 2024-01-24 23:47:18 回复(0)

Python3

可道非常道

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return bool布尔型
#
class Solution:
    def isValid(self , s: str) -> bool:
        # write code here
        stack = []  # 用于存储左括号
        mapping = {')': '(', '}': '{', ']': '['}  # 定义括号对应关系
        
        for char in s:
            if char in mapping:  # 若当前字符为右括号
                if not stack&nbs***bsp;stack[-1] != mapping[char]:
                    return False  # 若栈为空或栈顶元素与当前右括号不匹配，则返回False
                stack.pop()  # 匹配成功，弹出栈顶的左括号
            else:
                stack.append(char)  # 若当前字符为左括号，压入栈中
        
        return not stack  # 若栈为空，则表示所有括号都已匹配完全，返回True，否则返回False

发表于 2023-10-18 11:09:57 回复(0)

Python3

LeoAlan

# 解法一
class Solution:
    def isValid(self, s: str) -> bool:
        # 循环替换，直到字符串为空或者不变
        while True:
            ori = s
            s = s.replace("()", "").replace("{}", "").replace("[]", "")
            # 如果字符串为空，则为True
            if not s:
                return True
            # 如果字符串不再发生变化，则为False
            if s == ori:
                return False


# 解法二
class Solution:
    def isValid(self, s: str) -> bool:
        # 定义一个映射关系
        def judge_duichen(s1, s2):
            mapping = {"}": "{", ")": "(", "]": "["}
            return True if s2 in mapping and mapping[s2] == s1 else False

        # 定义一个列表，用来存储当前入栈的元素
        all = []
        for i in s:
            # 如果当前栈为空，则将当前元素入栈，并且跳到下一次循环
            if not all:
                all = [i]
                continue
            # 如果当前元素与栈顶元素对称，则将栈顶元素出栈
            if judge_duichen(all[-1], i):
                all.pop()
            # 如果不对称，则将当前元素入栈
            else:
                all.append(i)
        # 如果栈为空，则为True，否则为False
        return all == []


# 解法三：
class Solution:
    def isValid(self, s: str) -> bool:
        all = []
        mapping = {"}": "{", ")": "(", "]": "["}
        # 先让所有的左括号入栈
        for i in s:
            if i in "{[(":
                all.append(i)
            # 如果当前元素是右括号，且栈为空，则返回False，因为右括号不能先于左括号出现
            elif all == []:
                return False
            # 如果当前元素是右括号，则判断栈顶元素是否与其对称，如果对称，则将栈顶元素出栈，否则返回False
            elif mapping[i] == all[-1]:
                all.pop()
            else:
                return False
        # 在循环结束后，如果栈为空，则为True，否则为False
        return all == []

发表于 2023-09-17 11:48:44 回复(0)

Python3

zackw

class Solution:
    def isValid(self , s: str) -> bool:
        # write code here
        if len(s)%2 == 1:
            return False
        else:
            stack = []  # 左括号入栈，右括号没必要入栈，入了后续也不可能匹配上
            pairs = ["()","[]","{}"]
            for i in range(len(s)):
                if s[i] in "({[":
                    stack.append(s[i])
                else:   #输入的是右括号
                    if len(stack) == 0:
                        return False    # 栈里没有左括号和右括号匹配
                    else:
                        pair = stack[-1]+s[i]
                        if pair in pairs:
                            stack.pop(-1)   # 匹配成功则弹出栈里的最后一个左括号
                        else:
                            return False # 如果栈里最后一个左括号和右括号不匹配则永远不会匹配上了
            if len(stack) == 0: # 判断所有左括号是否全部出栈
                return True
            else:
                return False

发表于 2023-09-12 20:09:47 回复(0)

Python3

不刷题怎么进大厂

请问为什么我的代码会提示列表越界？

class Solution:

def isValid(self , s: str) -> bool:

# write code here

n = len(s)

if n%2 != 0:

return False

ls = []

for a in range(n):

while a<n and (s[a] == '(' or s[a] == '[' or s[a] == '{'):

ls.append(s[a])

a += 1

if s[a] == ')' and ls[-1] == '(':

ls.pop()

elif s[a] == ']' and ls[-1] == '[':

ls.pop()

elif s[a] == '}' and ls[-1] == '{':

ls.pop()

if not ls:

return True

else :

return False

发表于 2023-07-05 00:16:56 回复(1)

Python3

牛客292060878号

class Solution:
    def isValid(self , s: str) -> bool:
        # write code here
        if not s:
            return True
        if s[0] == ')'&nbs***bsp;s[0] == ']'&nbs***bsp;s[0] == '}':
            return False
        if len(s) % 2 == 1:
            return False
        ss = []
        for i in s:
            if i == '('&nbs***bsp;i == '['&nbs***bsp;i == '{':
                ss.append(i)
            else:
                if not ss:
                    return False
                p = ss.pop()
                if (i == ')' and p == '(')&nbs***bsp;(i == ']' and p == '[')&nbs***bsp;(i == '}' and p == '{'):
                    flag = 1
                else: 
                    return False
        if ss:
            return False
        return True

easy

发表于 2022-12-10 19:38:17 回复(0)

Python3

Joy_9

class Solution:
    def isValid(self , s: str) -> bool:
        dic={"}":"{",")":"(","]":"["}
        half=[]
        for v in s:
            if v in '{([':
                half.append(v)
            elif v in ']})':
                if len(half)>0 and dic[v]==half[-1]:
                    half.pop()
                else:
                    return False
        return len(half)==0

发表于 2021-12-28 03:37:38 回复(0)

Python3

悠悠小水草

class Solution:
    def isValid(self , s ):
        d = {'}': '{', ']': '[', ')': '('}
        stack = []
        for char in s:
            if char in '{[(':
                stack.append(char)
            if char in '}])':
                if not stack:
                    return False
                else:
                    if d[char] == stack[-1]:
                        stack.pop()
                    else:
                        return False
        return not stack

发表于 2021-09-05 23:35:22 回复(0)

Python3

刺猬她很瘦

class Solution:
    def isValid(self , s ):
        # write code here
        # 栈原理
        result = []
        try :
            for i in s :
                if i == '['&nbs***bsp;i == '('&nbs***bsp;i == '{' :
                    result.append(i)
                    print(result)
                elif i == ']' and result[-1] == '[' :
                    result.pop()
                elif i == ')' and result[-1] == '(' :
                    result.pop()
                elif i == '}' and result[-1] == '{' :
                    result.pop()
        except :
            return False
        if result == [] :
            return True 
        else :
            return False

发表于 2021-08-24 15:10:04 回复(0)