题目
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
解题
public boolean isValid(String s) {
//先用map把括号对存起来，key：左括号；value：右括号；
// 这样配对起来时间复杂度就为O(1);
//防止栈为空时报错，加入('?','?')
Map<Character,Character> map = new HashMap<Character,Character>();
map.put('(',')');
map.put('[',']');
map.put('{','}');
map.put('?','?');
//排除几种特殊情况：
if(s.equals("")){
return true;
}
if(s.length()%2==1){
return false;
}
if(s.charAt(0)==')'||s.charAt(0)==']'||s.charAt(0)=='}'){
return false;
}
//初始化栈，然后循环s,如果是左括号，先入栈，并且把它放在stack的last；
//如果有跟它配对的右括号出现，就将它移除，如果最后正好都配对完，剩下的就是最开始的那个'？'
LinkedList<Character> stack = new LinkedList<Character>();
stack.add('?');
for(Character c:s.toCharArray()){
//map如果包含key，证明就还是左括号
if(map.containsKey(c)){
stack.addLast(c);
// map不包括key了，那证明应该是出现了一个右括号，如果符合一对括号，
// 那它和栈里面的最后一个括号之间，肯定不能有其他形式的括号
// 所以把栈里的最后一个从map里get出来，看是否跟右括号一样
}else if(map.get(stack.removeLast())!=c){
return false;
}
}
return stack.size()==1;
}
j结果
执行用时 :5 ms, 在所有 Java 提交中击败了79.77%的用户
内存消耗 :35.1 MB, 在所有 Java 提交中击败了82.28%的用户
