有效的括号(leetcode20)
有效的括号(leetcode20)
Vincent-yuan
发布于 2021-02-25 17:00:32
发布于 2021-02-25 17:00:32
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
示例1：
输入：s = "()[]{}"
输出：true示例2：
输入：s = "([)]"
输出：false分析：
使用栈
当我们遇到一个右括号时，栈顶需要有一个对应的左括号来闭合。
如果栈中没有左括号或者类型不相同，则字符串无效。
我们使用哈希表存储每一种括号，其中哈希表的键为右括号，值为相同类型的左括号。
遍历结束后，如果栈中没有左括号，说明我们将字符串s中的所有左括号闭合，返回true,否则返回false;
注意到有效字符串的长度一定是偶数，因此如果字符串长度是奇数，直接返回false;
代码：
public class leetcode20 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
String input = in.nextLine();
System.out.println(isValid(input));
}
public static boolean isValid(String s) {
int n = s.length();
//如果长度为奇数，则直接返回false
if(n%2==1){
return false;
}
//用哈希表存储每一种括号，哈希表的键为右括号，值为相同类型的左括号
Map<Character,Character> pairs = new HashMap<Character,Character>(){
{
put(')','(');
put(']','[');
put('}','{');
}
};
Stack<Character> stack = new Stack<Character>();
for(int i=0;i<n;i++){
char ch = s.charAt(i);
if(pairs.containsKey(ch)){//字符为右括号时，判断
//如果此时栈为空，或者栈顶元素与字符对应哈希表中的值不相同，则返回false
if(stack.isEmpty()||stack.peek()!=pairs.get(ch)){
return false;
}
stack.pop();
}else{//字符为左括号时，加入栈中
stack.push(ch);
}
}
return stack.isEmpty();
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-02-23 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读