LeetCode20有效的括号

LeetCode20有效的括号

/**
 * Date:2022/04/17 12:57
 *
 * @author 小豆子
 * @version 1.0
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 *  
 *
 * 示例 1：
 *
 * 输入：s = "()"
 * 输出：true
 * 示例 2：
 *
 * 输入：s = "()[]{}"
 * 输出：true
 * 示例 3：
 *
 * 输入：s = "(]"
 * 输出：false
 * 示例 4：
 *
 * 输入：s = "([)]"
 * 输出：false
 * 示例 5：
 *
 * 输入：s = "{[]}"
 * 输出：true
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
 public class Solution {
    
    public boolean isValid(String s){
        //先取出length,防止多次取,徒增消耗
        int n = s.length();
        //字符串长度为奇数则不可能有效
        if (n % 2 == 1) {
            return false;
        }
        //方便判断当前符号是左还是右括号
        HashMap<Character, Character> map = new HashMap<>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');
        //deque是栈,先进后出
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            char at = s.charAt(i);
            //如果是右括号,则符合条件的字符串的前一个字符一定是 相对应的左括号 ()[]{},([])符合  {(})不符合
            if (map.containsKey(at)){
                //如果此时栈为空,表示它前面没左括号入栈,也就没左括号,直接false
                //如果此时栈不为空,但前面入栈的不是与它对应的左括号,直接false
                if (stack.isEmpty() || stack.peek() != map.get(at)){//peek(),返回最顶上刚入栈的值,但不删除
                    return false;
                }
                stack.pop();//取出最顶上的值,并删除
            } else {//左括号,直接入栈
                stack.push(at);
            }
        }

        return stack.isEmpty();
    }
}