字符串中只含有括号 (),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式,从内到外必须是<>,(),[],{},例如。输入: [()] 输出:YES,而输入([]), ([])都应该输出NO。
时间: 2023-11-25 08:29:40 浏览: 70
判断输入的表达式中括号是否配对
5星 · 资源好评率100%
这是一个典型的栈的应用。我们可以遍历输入的字符串,遇到左括号就将其压入栈中,遇到右括号就判断其是否与栈顶的左括号匹配,如果匹配则将栈顶的左括号出栈,继续遍历字符串;如果不匹配则说明括号不匹配,直接返回NO。最后如果栈为空,则说明所有左括号都有与之匹配的右括号,返回YES,否则返回NO。
以下是代码实现(Python):
```python
def is_valid(s: str) -> bool:
stack = []
mapping = {')': '(', ']': '[', '}': '{', '>': '<'}
for char in s:
if char in mapping.values():
stack.append(char)
elif char in mapping.keys():
if not stack or stack[-1] != mapping[char]:
return False
stack.pop()
return not stack
```
时间复杂度为O(n),空间复杂度为O(n)。
阅读全文