有效的括号(20)

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

大体思路

这里我们使用栈这个数据结构来解决，我们从左到右依次遍历，如果是左括号我们就添加一个对应的右括号进入到栈中，然后当我们遍历到右括号的时候我们需要比对当前栈顶元素是不是和当前遍历到的右括号一致，如果一致则弹出栈，如果不一致则说明此时闭合没按照顺序进行和我们的题目要求的不一致，如果我们遍历到栈为空，而此时我们还有括号元素没有遍历完，则说明此时没有左括号来和剩余的右括号进行匹配了，也是不符合题目要求的

代码解析

class Solution {
    public boolean isValid(String s) {

        if (s.length() == 1) {
            return false;
        }

        Map<Character, Character> zuo = new HashMap<>();
        zuo.put('(', ')');
        zuo.put('{', '}');
        zuo.put('[', ']');
        Map<Character, Character> you = new HashMap<>();
        you.put(')', '(');
        you.put('}', '{');
        you.put(']', '[');

        //这是作为一个判断依据，如果你这这个S中全都是左括号的话就返回false;
        boolean temp = false;
        Stack<Character> stack = new Stack<>();
        //这里如果是上来就是右括号开头的就不符合题目要求，直接返回
        if (you.containsKey(s.charAt(0))) {
            return false;
        }
        for (int i = 0; i < s.length(); i++) {
            if (zuo.containsKey(s.charAt(i))) {
                stack.push(zuo.get(s.charAt(i)));
            } else {
                //到这里已经说明S中包含右括号了，不全是左括号了
                temp = true;

                //这里是判断栈如果为空，但此时S中还有元素没有遍历完，那就不能按照我们题目要求的顺序进行闭合了，我们直接返回false
                if (stack.isEmpty() && i <= s.length() - 1) {
                    return false;
                } else if (s.charAt(i) == stack.peek()) {
                    stack.pop();
                    continue;
                } else {
                    return false;
                }
            }
        }

        if (temp == false || !stack.isEmpty()) {
            return false;
        }

        return true;
    }
}