字符串中只含有括号 (),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式,从内到外必须是<>,(),[],{},例如。输入: [()] 输出:YES,而输入([]), ([])都应该输出NO。
时间: 2023-11-25 14:29:40 浏览: 20
这是一个经典的栈的应用。我们需要用到一个栈来维护左括号,遇到左括号就将其压入栈中,遇到右括号就判断其是否与栈顶的左括号匹配,如果匹配则将栈顶的左括号出栈,继续遍历字符串;如果不匹配则说明括号不匹配,直接返回NO。最后如果栈为空,则说明所有左括号都有与之匹配的右括号,返回YES,否则返回NO。
但是本题有一个限制条件,就是括号有互相包含的形式,从内到外必须是<>,(),[],{},因此我们需要对栈的操作进行修改。具体来说,每当遇到左括号时,我们首先将其与栈中的上一个元素进行匹配,如果可以匹配则将两个元素一起压入栈中,否则只将当前左括号压入栈中。当遇到右括号时,我们取出栈顶的元素,如果其与当前右括号匹配,则继续遍历字符串;否则说明括号不匹配,直接返回NO。最后如果栈为空,则说明所有左括号都有与之匹配的右括号,返回YES,否则返回NO。
以下是代码实现(Python):
```python
def is_valid(s: str) -> bool:
stack = []
mapping = {')': '(', ']': '[', '}': '{', '>': '<'}
for char in s:
if char in mapping.values():
if stack and stack[-1] in mapping.keys() and mapping[char] == stack[-1]:
stack.pop()
stack.append(char+mapping[char])
else:
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)。