Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"

Output: true

Example 2:

Input: "()[]{}"

Output: true

Example 3:

Input: "(]"

Output: false

Example 4:

Input: "([)]"

Output: false

Example 5:

Input: "{[]}"

Output: true


要求判断括号是否匹配，我们用一个stack来存储，然后用map存储对应的括号序列
每次往栈里添加元素时，通过map判断是左括号[还是右括号]，如果是右括号，可以通过map判断出来，就从
stack中pop出栈顶元素来和当前括号匹配，如果不匹配则说明整个序列都不匹配，如果是左括号就继续加入到stack中

class Solution {

    public boolean isValid(String s) {

        Stack<Character> stack=new Stack<Character>();

        Map<Character,Character> map=new HashMap<Character,Character>();

        map.put(')','(');

        map.put('}','{');

        map.put(']','[');

        for(int i=0;i<s.length();i++){

            char c=s.charAt(i);

            if(map.containsKey(c)){

                char temp=stack.empty()? '#':stack.pop();

                if(temp!=map.get(c)) return false;

            }else stack.push(c);

        }

        return stack.isEmpty();

    }

}