20. 有效的括号
给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false
class Solution {
public boolean isValid(String s) {
if (s.length() % 2 != 0) {
return false;
}
s = s.replace("()", "");
s = s.replace("{}", "");
s = s.replace("[]", "");
return s.length() == 0;
}
}
该方法不太全面，法二会更好一些
class Solution {
public boolean isValid(String s) {
Stack<Character> st = new Stack<>();
if (s.length() % 2 != 0) {
return false;
}
for (char c : s.toCharArray()) {
switch (c) {
case '(' :
st.push(')');
break;
case '{' :
st.push('}');
break;
case '[' :
st.push(']');
break;
default:
if (st.isEmpty() || st.pop() != c) {
return false;
}
}
}
return st.isEmpty();
}
}
用栈 + 奇偶校验：
当字符串的长度是奇数时，说明有一个括号对一定是匹配不上的直接返回false
扫描字符，当遇到左括号时将对应的右括号压入栈中（当遇到右括号的时候，就不用还找括号的对应关系）
当遇到右括号的时候将栈顶的元素pop出来看一下，如果发现括号不一致，直接返回false
解释：因为一个合格的括号表达式当遇到第一个右括号的时候，栈顶的括号一定是匹配的
遍历完成之后，如果栈空返回true，否则返回false
Original: https://blog.csdn.net/starry_night_summer/article/details/127806046
Author: 余忆北
Title: leetcode 20
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/658042/
转载文章受原作者版权保护。转载请注明原作者出处！