算法题之有效括号问题

算法题之有效括号问题

题目描述

思路分析

思路图解

代码实现

public boolean isValid(String s) { //首先对s进行判断:(1)若s为空或者null,则表示有效字符串(2)若s的长度为奇数,则不可能满足要求,直接返回false if (s == null || s.length() == 0) return true; if (s.length() % 2 == 1) return false; //首先仍然是定义HashMap存储括号的对应信息 Map<Character,Character> map = new HashMap<>(); map.put('(',')'); map.put('[',']'); map.put('{','}'); map.put('*','*');//多定义一个辅助key,作为字符串出现()[]{}}{,当出栈出栈到}{时,此时判断}时,栈内部没有元素,发生java.util.NoSuchElementException //如果字符串的第一个字符即为')',']','}'则一定不符合要求 if(s.length() > 0 && !map.containsKey(s.charAt(0))) return false; //定义一个栈(用链表定义),来进行有效括号的入栈和出栈操作 //LinkedList<Character> stack = new LinkedList<>(); Stack<Character> stack = new Stack<>(); stack.push('*'); for (int i = 0; i < s.length(); i++) { char val = s.charAt(i); //判断map中是否包含此key if (map.containsKey(val)) { //包含则将其进行入栈操作 stack.push(val); //不包含,则为'}',')',']'等符号,然后此时栈底元素是否为对应的'{','(','[',若不是则返回false }else if (map.get(stack.pop()) != val) { return false; } } //最后如果遍历结束,stack若为1(刚开始添加的辅助key'*')则表示符合要求,不为1则表示不符合要求 return stack.size() == 1; }