LeetCode20. 有效的括号🌟🌟🌟🌟🌟简单
课后作业
问题描述
原文链接：20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
代码实现
Java
class Solution {
public boolean isValid(String s) {
if(s.length() % 2 == 1){
return false;
}
Stack<Character> stack = new Stack();
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == '('){
stack.push(')');
} else if(s.charAt(i) == '{'){
stack.push('}');
} else if(s.charAt(i) == '['){
stack.push(']');
} else {
if(stack.isEmpty() || stack.pop() != s.charAt(i)){
return false;
}
}
}
return stack.isEmpty();
}
}
Python
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
if len(s) % 2 == 1:
return False
stack = []
for i in range(len(s)):
if s[i] == '(':
stack.append(')')
elif s[i] == '{':
stack.append('}')
elif s[i] == '[':
stack.append(']')
else:
if not stack or stack.pop() != s[i]:
return False
return not stack
C++
class Solution {
public:
bool isValid(string s) {
if(s.length() % 2 == 1){
return false;
}
stack<char> st;
for(int i = 0; i < s.length(); i++){
if(s[i] == '('){
st.push(')');
} else if(s[i] == '{'){
st.push('}');
} else if(s[i] == '['){
st.push(']');
} else {
if(st.empty() || st.top() != s[i]){
return false;
}
st.pop();
}
}
return st.empty();
}
};
Go
type stack []byte
func (s *stack) Push(b byte) {
(*s) = append((*s), b)
}
func (s *stack) Pop() byte {
res := (*s)[len(*s)-1]
(*s) = (*s)[:len(*s)-1]
return res
}
func isValid(s string) bool {
if len(s)%2 == 1 {
return false
}
st := make(stack, 0)
for i := 0; i < len(s); i++ {
if s[i] == '(' {
st.Push(')')
} else if s[i] == '{' {
st.Push('}')
} else if s[i] == '[' {
st.Push(']')
} else {
if len(st) == 0 || st.Pop() != s[i] {
return false
}
}
}
return len(st) == 0
}
评论(4)
打卡st;
class Solution {
public:
bool isValid(string s) {
stack
//剪枝，奇数元素必不可能
if(s.size()%2!=0){
return false;
}
};
/*
1、思路：
– 左括号：无脑压栈，压入右括号
– 右括号：看看是否相等，不相等则无效，相等弹栈
2、不可能的情况：
– 奇数个元素
– 偶数个元素：左括号多、右括号多、左右不闭合
2、string可以使用下标索引
*/
为什么二者调换顺序就是错误的呢？
打卡