2.给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。有效字符串需满足:(1)左括号必须用相同类型的右括号闭合。(2)左括号必须以正确的顺序闭合。(3)每个右括号都有一个对应的相同类型的左括号。
时间: 2024-01-31 22:58:15 浏览: 25
思路:
使用栈来解决问题,遍历字符串,如果遇到左括号,将其入栈,如果遇到右括号,判断栈顶元素是否与其匹配,如果匹配则弹出栈顶元素,否则返回 False。最后,如果栈为空,则表示字符串有效。
代码实现:
class Solution:
def isValid(self, s: str) -> bool:
stack = []
for c in s:
if c in ['(', '[', '{']:
stack.append(c)
else:
if not stack:
return False
if c == ')' and stack[-1] == '(':
stack.pop()
elif c == ']' and stack[-1] == '[':
stack.pop()
elif c == '}' and stack[-1] == '{':
stack.pop()
else:
return False
return not stack
相关问题
给定一个只包括‘(’, ‘)’, ’{‘, ‘}’, ‘[’, ’]”的字符串 s , 判断字符串是否合法。
给定一个只包括‘(’, ‘)’, ’{‘, ‘}’, ‘[’, ’]”的字符串 s,判断字符串是否合法的方法是使用栈来进行匹配。遍历字符串s,当遇到左括号时,将其入栈;当遇到右括号时,判断栈顶元素是否与当前右括号匹配,如果匹配则将栈顶元素出栈,否则返回false。最后,如果栈为空,则说明字符串合法,否则返回false。
以下是判断字符串是否合法的示例代码:
```python
def isValid(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
if not stack or stack[-1] != mapping[char]:
return False
stack.pop()
else:
stack.append(char)
return not stack
s = input("请输入字符串:")
if isValid(s):
print("字符串合法")
else:
print("字符串不合法")
```
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。的c++代码
以下是使用滑动窗口算法实现的 C++ 代码:
```c++
#include <unordered_set>
int lengthOfLongestSubstring(string s) {
int n = s.size();
unordered_set<char> set;
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
if (set.find(s[j]) == set.end()) {
set.insert(s[j++]);
ans = max(ans, j - i);
} else {
set.erase(s[i++]);
}
}
return ans;
}
```
该算法使用双指针维护一个滑动窗口,滑动窗口中存储的是当前不含重复字符的子串。使用 `unordered_set` 来判断是否出现重复字符,如果出现重复字符,则将左指针向右移动一位,并从集合中删除对应的字符。如果没有出现重复字符,则将右指针向右移动一位,并将新的字符加入集合中。最后返回最长子串的长度。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)