力扣hot100：有效的括号

题目描述：

解题思路：

栈先入后出特点恰好与本题括号排序特点一致，即若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空；
建立哈希表 dic 构建左右括号对应关系：key 左括号，value 右括号；这样查询 2 个括号是否对应只需 O(1) 时间复杂度；建立栈 stack，遍历字符串 s 并按照算法流程一一判断。
算法流程

如果 a 是左括号，则入栈 push；
否则通过哈希表判断括号对应关系，若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 c 不对应，则提前返回 false。

代码：

class Solution { private static final Map<Character,Character> map=new HashMap<Character,Character>(); static{ map.put('{','}'); map.put('[',']'); map.put('(',')'); map.put('?','?'); } public boolean isValid(String s) { if(s.length()>0&&!map.containsKey(s.charAt(0))){ return false; } LinkedList<Character> stack=new LinkedList<Character>(); stack.add('?'); for(Character a:s.toCharArray()){ if(map.containsKey(a)){ stack.addLast(a); } else if(map.get(stack.removeLast())!=a){ return false; } } return stack.size()==1; } }

代码解析：

本题用链表代替栈的结构，入栈对应stack.addLast(a);，出栈对应stack.removeLast()。