python有效的括号
时间: 2023-11-16 10:57:24 浏览: 46
Python有效的括号是一个判断字符串中括号是否匹配的问题。给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。如果字符串中的括号是按照正确的顺序匹配的,则返回 True,否则返回 False。这个问题可以使用栈来解决。我们可以遍历字符串中的每一个字符,如果是左括号,则将其压入栈中,如果是右括号,则将栈顶的左括号弹出,判断是否匹配。如果不匹配,则返回 False,如果匹配,则继续遍历。最后,如果栈为空,则说明所有的括号都匹配,返回 True,否则返回 False。
下面是一个Python的解法,时间复杂度为O(n),空间复杂度为O(n):
```
class Solution:
def isValid(self, s: str) -> bool:
if len(s) % 2 == 1:
return False
pairs = { ")": "(", "]": "[", "}": "{" }
stack = list()
for ch in s:
if ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
else:
stack.append(ch)
return not stack
```
其中,pairs是一个字典,用来存储每一种右括号对应的左括号。stack是一个栈,用来存储左括号。遍历字符串中的每一个字符,如果是左括号,则将其压入栈中,如果是右括号,则将栈顶的左括号弹出,判断是否匹配。如果不匹配,则返回 False,如果匹配,则继续遍历。最后,如果栈为空,则说明所有的括号都匹配,返回 True,否则返回 False。