栈算法之【有效括号】

目录

LeetCode-20题

LeetCode-20题

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

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

class Solution {public boolean isValid(String s) {// checkif (s == null || s.length() < 2)return false;// map的key表示左括号，value表示右括号Map<Character, Character> cache = new HashMap<>();cache.put('(', ')');cache.put('{', '}');cache.put('[', ']');// 借助LinkedList实现的栈LinkedList<Character> stack = new LinkedList<>();for (int i = 0; i < s.length(); i++) {char curr = s.charAt(i);if (cache.containsKey(curr)) {// 如果是左括号，就将其对应的右括号入栈stack.push(cache.get(curr));} else {// 如果是右括号if (!stack.isEmpty() && stack.peek() == curr) {// 此时栈不为空，且栈顶元素就是当前的右括号，执行出栈操作stack.pop();} else {return false;}}}// 此时栈空了就表示s是有效括号return stack.isEmpty();}
}