给定一个字符串,仅由'('和')','{'和'}','['和']'组成,请问这个字符串是否是一个合法的括号序列? 输入 一行一个字符串,长度小于2000 输出 输出Yes或No 样例输入 Copy ()([]){} 样例输出 Copy Yes
时间: 2023-08-12 17:06:33 浏览: 112
js-utils-给定两个字符串s和t
好的,我理解了你的问题。这个问题可以用栈来解决。
首先,我们定义一个栈,遍历字符串中的每个字符。如果当前字符是左括号,则将其推入栈中;如果当前字符是右括号,则将栈顶元素弹出并检查是否与当前字符匹配。如果不匹配,则该字符串不是合法的括号序列。
如果遍历完字符串后栈为空,则该字符串是合法的括号序列,否则不合法。
下面是一个 Python 代码示例:
```python
def is_valid(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stack
s = input()
if is_valid(s):
print("Yes")
else:
print("No")
```
注意,这个算法的时间复杂度是 $O(n)$,其中 $n$ 是字符串的长度。
阅读全文