LeetCode-20-有效的括号
# LeetCode-20-有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例2：
输入: "()[]{}"
输出: true
示例3：
输入: "(]"
输出: false
示例4：
输入: "([)]"
输出: false
示例5：
输入: "{[]}"
输出: true
# 解题思路
方法1、栈：
观察题目可知，要想构成有效的括号，最开始加入的(括号的反)必须是最后加入
这种规律符合栈的先进后出的方式，于是可以用栈来模拟
当扫描到前括号(、{、[的时候，在栈中加入对应的反括号),},]
当全部匹配时，栈为空等于true
特例处理当输入的字符为null的时候，直接返回true
当输入的字符为[的时候，栈中会加入反括号]，此时栈不为空，返回false
当输入的字符为]的时候，栈中不会加入反括号，此时如果直接返回栈是否为空，会返回true，但这是一个错误的结果
所以新增一个新的判断，else if(stack.isEmpty()||c!=stack.pop())联合判别反括号和栈空的情况，都是false
# Java代码
class Solution {
public boolean isValid(String s) {
if(s==null||s.length()==0) return true;
Stack<Character> stack = new Stack<>();
char[] cs = s.toCharArray();
for(char c:cs){
if(c=='('){
stack.push(')');
}else if(c=='{'){
stack.push('}');
}else if(c=='['){
stack.push(']');
}else if(stack.isEmpty()||c!=stack.pop()){
return false;
}
}
return stack.isEmpty();
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-06-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
