题目
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
一共有3种括号。每种括号可分为左括号和右括号。我们可以模拟一个匹配的过程，没有右括号都应和一个左括号匹配上。可以依次遍历这些括号，遇到左括号时，我们不知道是否有右括号和它匹配，所以应该把它暂存起来。遇到右括号时，这时前面必须有一个正确的左括号和它匹配。
对于第一个遇到的右括号，和它匹配的一定是之前最后遇到的一个左括号，如果该左括号不匹配或不存在，说明匹配失败。
如果能匹配成功，我们消去这一对括号。继续判断下一个括号的情况。再遇到右括号，继续找之前的最后一个左括号（注意这里已经去掉了匹配成功的括号，所以还是满足和最后一个左括号匹配的条件）。
用一个stack存储左括号。
代码
class Solution {
private static Map<Character,Character> map = new HashMap<Character,Character>();
static {
map.put(')','(');
map.put('}','{');
map.put(']','[');
}
public boolean isValid(String s) {
LinkedList<Character> stack = new LinkedList<Character>();
int length = s.length();
for(int i = 0; i < length; i++) {
char c = s.charAt(i);
if(map.containsKey(c)) {
char c1 = stack.isEmpty()? '#' : stack.pop();
if(!map.get(c).equals(c1)) {
return false;
}
} else {
stack.push(c);
}
}
return stack.isEmpty();
}
}
知识点
1.LinkedList可以作为栈使用。可以直接调用它的push和pop方法。
