数据结构与算法

栈--有效的括号

2019-12-18  本文已影响0人  暮想sun

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

输入: "{[]}"
输出: true

 public static Boolean isValidBracket(String s) {

        if (s == null || "".equals(s)) {
            return true;
        }

        //长度必须为偶数,才可能是有效字符串
        int length = s.length();
        if (length % 2 != 0) {
            return false;
        }

        Map<Character, Character> map = new HashMap<>(16);
        map.put(')','(');
        map.put(']', '[');
        map.put('}', '{');
        //将字符串数据入栈
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < length; i++) {

            Character c = s.charAt(i);

            //如果是右括号,则判断与栈顶元素是否匹配
            if(map.containsKey(c)){
                //遇到右括号,栈内元素是空,不成功
                if(stack.isEmpty()){
                    return false;
                }

                //栈顶元素弹出,匹配成功,则继续
                if(!map.get(c).equals(stack.pop())){
                    return false;
                }

                continue;
            }


            //左括号入栈
            stack.push(c);
        }
        //栈内非空,则失败
        return stack.isEmpty();
    }
上一篇下一篇

猜你喜欢

热点阅读