链接：LeeCode 20
题目：
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例：
输入：s = “{[]}”
输出：true
输入：s = “([)]”
输出：false
方法一： 使用辅助栈和HashMap
思路：
用HashMap放入成对的括号，由于要用get()方法 通过右括号得到对应的左括号，所以右括号为 key ，左括号为value；
遍历输入的String，左括号则压栈；
如果是右括号，当栈不为空，&& 栈顶peek() = 右括号对应的左括号才弹出！ 否则 return false
class Solution {
public boolean isValid(String s) {
if( (s.length()%2)!=0 ){ //非成对即余数不为0，则直接false
return false;
}
Map<Character,Character> m=new HashMap<>();
//要用get方法，通过右括号找左括号，所以key放右括号，value放左括号！
m.put(')','(');
m.put('}','{');
m.put(']','[');
Stack<Character> stack=new Stack<>(); //栈
for(int i=0;i<s.length();i++){
//转换为字符
char c=s.charAt(i);
if(m.containsValue(c)){ //如果是左括号，压栈
stack.push(c);
}else if(m.containsKey(c)){ //如果是右括号,比较
if( !stack.isEmpty() && stack.peek()==m.get(c)){ //栈不为空，且栈顶=右括号对应的左括号才弹出！ 否则 return false
stack.pop();
}else{
return false;
}
}else{ // 如果都不是，直接false
return false;
}
}
return stack.isEmpty(); //栈为空则true，不为空则false
}
}
注意;此处必须是右括号和栈顶成对，这样才满足括号以正确的顺序闭合，如：“([)]” 是错误的，未按正确的顺序闭合。
如果是成对的括号，那么遍历到右括号时，栈顶一定是对应类型的左括号！
简化：
class Solution {
public boolean isValid(String s) {
//
HashMap<Character,Character> h=new HashMap<>();
h.put(')','(');
h.put('}','{');
h.put(']','[');
Stack<Character> stack=new Stack<>();
//
for(int i=0;i<s.length();i++){
Character c=s.charAt(i);
// left
if(h.containsValue(c)){
stack.push(c);
}else{ // right
if(!stack.isEmpty() && h.get(c)==stack.peek()){
stack.pop();
}else{
return false;
}
}
}
return stack.isEmpty();
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89378.html
