2. 判断是否有效的括号 给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号
时间: 2024-11-03 20:23:53 浏览: 33
判断一个括号字符串的有效性通常采用栈数据结构来解决。遍历输入字符串`s`的过程中,我们按照以下规则操作:
1. 当遇到左括号('(', '{', '[')时,将其压入栈中。
2. 当遇到右括号时,检查栈顶元素是否与当前右括号匹配(例如,'(' 对应 ')','{' 对应 '}','[' 对应 ']')。如果匹配,将栈顶的左括号弹出;如果不匹配,则返回false,因为存在不正确的括号配对。
3. 遍历结束后,如果栈为空,说明所有括号都已正确配对,字符串有效,返回true。若栈非空,意味着还有未找到对应右括号的左括号,因此无效,返回false。
这里的关键在于维护栈的平衡,并确保左括号总是先于其对应的右括号出现。下面是一个简单的伪代码示例:
```python
def isValid(s):
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for char in s:
if char in pairs.values(): # 遇到左括号
stack.append(char)
elif char in pairs.keys(): # 遇到右括号
if not stack or stack.pop() != pairs[char]: # 栈顶不是匹配的左括号
return False
return len(stack) == 0 # 检查栈是否为空
# 使用示例
s = "({[]})"
print(isValid(s)) # 输出:True
```
阅读全文