给定一个只包括,(,’’,’”, ”,’[”, ” 的字符串 s ,判断字符串是否有效 有效字符串需满足: 1.左括号必须用相同类型的右括号闭合 2.左括号必须以正确的顺序闭合。 3.每个右括号都有一个对应的相同类型的左括号
时间: 2023-11-24 18:05:11 浏览: 49
可以使用栈来解决这个问题。我们遍历字符串 s 中的每一个字符,如果是左括号,将其压入栈中。如果是右括号,判断栈顶元素是否与之匹配,如果匹配,则弹出栈顶元素;否则返回 False。最后,如果栈为空,则说明所有左括号都有相应的右括号,返回 True;否则返回 False。
以下是 Python 代码的示例:
```python
def isValid(s: str) -> bool:
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for c in s:
if c in mapping:
if not stack or stack[-1] != mapping[c]:
return False
stack.pop()
else:
stack.append(c)
return not stack
```
时间复杂度为 O(n),其中 n 是字符串 s 的长度。
相关问题
给定两个字符串s和t判断s是否是t的子序列
题目描述:
给定两个字符串 s 和 t ,判断 s 是否为 t 的子序列。
示例:
s = "abc", t = "ahbgdc",返回 true
s = "axc", t = "ahbgdc",返回 false
思路:
遍历字符串 t,如果字符与 s 中的字符相同,则 s 中指针后移,直到 s 遍历完,返回 true。如果 t 遍历完,s 还没有遍历完,返回 false。
Python代码:
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
i, j = 0, 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1
j += 1
return i == len(s)
给定一个只包括,(,’)’的字符串 s,判断字符串是否有效,有效字符串需满足:
1. 左右括号必须成对出现。
2. 左括号必须先出现,右括号必须后出现。
3. 括号必须正确嵌套,即对于每一个左括号,必须有一个与之对应的右括号。
例如,字符串 "()" 、"(())" 和 "()()" 都是有效的,但是 "(()" 和 "())(" 不是有效的。
可以使用栈来解决这个问题。遍历字符串,当遇到左括号时,将其压入栈中,当遇到右括号时,从栈中弹出一个左括号,判断二者是否匹配。如果栈为空或者左右括号不匹配,则字符串无效。最后,如果栈中还有元素,则字符串也无效。
以下是 Python 代码实现:
```python
def isValid(s: str) -> bool:
stack = []
for c in s:
if c == '(':
stack.append(c)
elif c == ')':
if len(stack) == 0 or stack.pop() != '(':
return False
return len(stack) == 0
```