本文主要是介绍5.3有效的括号（LC20-E），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
算法：
题目中：左括号必须以正确的顺序闭合。意思是，最后出现的左括号（对应着栈中的最后一个元素），应该先找到对应的闭合符号（右括号）
比如:s="( [ ) ]"就是False，因为"("比"["先出现，对应地，"( [ "中最后的元素应该最先找到闭合符"]"，而 闭合符（就是右括号）先出现的是")"，这个时候就能判断False了
括号匹配是使用栈解决的经典问题。
由于栈结构的特殊性，非常适合做对称匹配类的题目。
首先要弄清楚，字符串里的括号不匹配有几种情况。
1.第一种情况：字符串里左方向的括号多余了 ，所以不匹配。
2.第二种情况：括号没有多余，但是 括号的类型没有匹配上。
3.第三种情况：字符串里右方向的括号多余了，所以不匹配。
怎么用栈来解决该问题？
举个例子：s="(","[","}",")"
遍历字符串中的符号，发现左括号时，往栈中push其对应的右符号；发现右括号时，往栈中pop与其一样的右括号
当遍历到"("，push“)” //stack=")"
当遍历到"["，push"]" //stack="]" , ")"
当遍历到"}"，push“}” //stack=“}”, "]" , ")"
当遍历到")", pop ")" //stack=“}”, "]"
发现stack非空，说明括号无效。
总的代码思路如下（遍历s中的符号item）：
1.如果 `item` 是一个开放符号（‘(’, ‘[’, ‘{’），则将相应的闭合符号压入栈中。
2.如果 `item` 是一个闭合符号（‘)’, ‘]’, ‘}’），则检查栈是否为空，或者栈顶元素（最后一个元素）与 `item` 不相等。
- 栈为空：说明没有右括号了，肯定不对了
- 栈顶元素（最后一个元素）与 `
item` 不相等：说明最近的需要的闭合符号不对（和示例一样） - 如果以上任一条件为真，则意味着闭合符号不平衡，函数返回 `
False`。
3.如果 `item` 是一个闭合符号，并且它与栈顶元素匹配，那么从栈中弹出顶部元素，表示开放符号和闭合符号是平衡匹配的。
4.在遍历完 `s` 中的所有字符后，如果栈为空，则表示所有的开放符号都已经匹配并弹出，函数返回 `True`。否则，如果栈不为空，则表示存在未匹配的开放符号，函数返回 `False`。
调试过程：
class Solution:def isValid(self, s: str) -> bool:stack = []for item in s:#如果s的长度为奇数，必然不符合，可以做个简单判断剪枝，节省时间if len(s)%2 != 0:return Falseelif item == "(":stack.append(")")elif item == "[":stack.append("]")elif item == "{":stack.append("}")#如果输入的不是以上三种左括号，那只能是右括号了#如果是右括号，正确的s对应的stack中应该存在该右括号了（刚刚append了）#如果此时stack为空，或者栈顶非距离最近的左括号的闭合符号，那就Falseelif not stack or item != stack[-1]:#注意：应该先判非空再判item != stack[-1]，因为若stack为空，stack[-1]不存在，判断时就会报错return Falseelse:stack.pop()return True if stack == None else False
原因：最后返回语句写得不对。栈为空应该用“stack == []”或者“len(stack)==0”表示。
在Python中，`None` 表示一个空对象，而 `[]` 表示一个空列表。在这段代码中，我们使用一个列表来模拟栈的数据结构。当栈为空时，我们希望栈对象 `stack` 的值是一个空列表 `[]`。
当使用 `stack == None` 进行判断时，它会检查栈对象 `stack` 是否是 `None`，而不是一个空列表。因此，如果栈为空，但是栈对象 `stack` 的值是 `None`，那么判断结果就会是错误的。
正确代码：
class Solution:def isValid(self, s: str) -> bool:stack = []for item in s:#如果s的长度为奇数，必然不符合，可以做个简单判断剪枝，节省时间if len(s)%2 != 0:return Falseelif item == "(":stack.append(")")elif item == "[":stack.append("]")elif item == "{":stack.append("}")#如果输入的不是以上三种左括号，那只能是右括号了#如果是右括号，正确的s对应的stack中应该存在该右括号了（刚刚append了）#如果此时stack为空，或者栈顶非距离最近的左括号的闭合符号，那就Falseelif not stack or item != stack[-1]:#注意：应该先判非空再判item != stack[-1]，因为若stack为空，stack[-1]不存在，判断时就会报错return Falseelse:stack.pop()return True if stack == [] else False时间空间复杂度：
- 时间复杂度: O(n)
- 空间复杂度: O(n)
这篇关于5.3有效的括号（LC20-E）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
