Valid Parentheses
你会得到一个字符串 s，它只由括号字符 (、)、[、]、{ 和 } 组成。当括号是平衡的时，返回 true：每个右括号都与最近一个尚未闭合的左括号配对，两者类型相同，并且最后没有未闭合的括号。否则返回 false。
函数
- sstring
- 要检查的括号字符串
- 返回值boolean
- 括号是否配对
约束条件
1 ≤ s.length ≤ 104s中只包含字符(、)、[、]、{和}。
示例
- 输入
- s = "[]{}()"
- 输出
- true
- 解释
- 三对括号并排放在一起，每一对都在打开后立即闭合。
- 输入
- s = "{[()()]}"
- 输出
- true
- 解释
- 两组圆括号在方括号内闭合，而方括号又在花括号内闭合。每个闭合符号都与当前仍未闭合的最近一个起始符号相匹配。
- 输入
- s = "{(})"
- 输出
- false
- 解释
}出现时，它后面打开的(还没有闭合，所以它闭合了错误类型的括号。
进阶
如果字符串中只包含圆括号，你能否不用栈，而是用单个计数器在 O(1) 额外空间内检查它？
提示
逐个打开提示，每个都会多透露一点。
从左向右读取字符串。当遇到右括号时，它可以匹配哪个左括号？
它只能闭合最近打开且仍未闭合的左括号。最后打开的括号最先闭合：这正是栈所遵循的顺序。
每遇到一个左括号，就将它压入栈中。遇到右括号时，栈不能为空，并且栈顶必须是同一种括号；将它弹出后继续。当字符串结束时，只有栈为空才表示括号平衡。
题解
只统计括号数量还不够：{(}) 中每种开括号和闭括号的数量都相同，但它仍然是错误的，因为顺序很重要。栈会按括号打开的顺序保存尚未闭合的括号，因此只需用栈遍历一遍，就能判断整个字符串是否正确。
重复移除匹配的成对元素
结果正确，但无法在最大的测试中运行完毕
思路
每个平衡字符串都有一对最内层的括号，中间没有任何内容，例如 {[()]} 中的 ()。删除相邻的匹配括号对不会改变字符串是否平衡。因此，不断重复删除，直到某一轮没有删除任何内容：平衡字符串会缩短为空字符串，而不平衡字符串会卡住并留下字符，例如 {(}) 从一开始就是这样。
每一轮都会扫描整个字符串并构建一个新的副本，而像 (((...))) 这样的嵌套字符串每轮会少一对括号。这最多需要 n/2 轮，每轮执行 O(n) 的工作，总计为 O(n²)。
算法
- 删除字符串中的所有
()、[]和{}。 - 如果这一轮没有删除任何内容，就停止。
- 否则，用更短的字符串重复操作。
- 如果字符串最终为空，则返回
true；如果还剩下任何括号，则返回false。
def isValid(s):
while True:
# Delete every adjacent matched pair in one round.
shorter = s.replace("()", "").replace("[]", "").replace("{}", "")
if shorter == s:
break # nothing left to delete
s = shorter
return s == ""使用栈进行一次遍历
思路
闭合括号必须匹配最近打开且尚未闭合的括号。最后打开的括号最先闭合，这种后进先出的顺序正是栈所遵循的。
将每个左括号对应等待匹配的右括号压入栈中。接下来，右括号必须与栈顶相同。如果栈为空，说明没有括号可供闭合；如果栈顶不同，说明右括号闭合了错误类型的括号，就像 } 在 {(}) 中那样，此时栈顶是 )。最后，栈中剩下的任何内容，例如 ((，都表示有括号已打开却从未闭合。每个字符只会入栈或出栈一次：时间复杂度为 O(n)，栈中最多有 n 个条目。
算法
- 创建一个空栈。
- 遇到左括号时，将与之匹配的右括号入栈。
- 遇到右括号时，如果栈为空或栈顶是其他字符，则返回
false；否则出栈。 - 处理完最后一个字符后，仅当栈为空时才返回
true。
def isValid(s):
closers = {'(': ')', '[': ']', '{': '}'}
stack = []
for ch in s:
if ch in closers:
stack.append(closers[ch])
elif not stack or stack.pop() != ch:
return False
return not stack
易错点和边界情况
- 分别统计每种括号的数量。
{(})中的括号数量相同，但它仍然无效；仅顺序不对，)(也会失败。 - 从空栈中弹出元素。如果字符串以右括号开头，例如
}或)]}，必须返回false，而不是崩溃。 - 跳过最后的检查。
(([{中不会遇到错误的右括号，因此只有检查剩余的栈才能发现它无效。 - 只相信长度。奇数长度始终无效，但偶数长度并不能证明任何事：
(]和())(都无效。 - 在移除元素的方法中，不要将括号未经转义就传给正则表达式或 Lua 模式。
(和[在其中有特殊含义；请使用纯文本替换。
常见问题3
有效括号的时间复杂度是多少？
栈解法的运行时间为 O(n)，因为每个字符最多只会被压入或弹出一次。在最坏情况下，也就是字符串只包含开括号时，它需要 O(n) 的空间。反复删除匹配的括号对需要 O(n²) 的时间，因为深度嵌套的字符串每轮只会减少一对括号。
为什么在“有效的括号”问题中使用栈？
括号可以嵌套，因此最后打开的括号必须最先闭合。栈会将这个括号放在顶部，你可以在常数时间内读取并移除它，从而让整个检查保持在 O(n)。
空字符串是有效的括号序列吗？
是的。空字符串没有未匹配的括号，因此是平衡的：栈会保持为空，移除循环没有任何内容需要移除。在这个问题中，s 至少有一个字符。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isValid(s):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "[]{}()"预期输出
true