题目：
20.有效的括号
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
题目来源：力扣（LeetCode）
能否写出：能写出来
时间：20分钟
思路：比较简单的一题，对初入门的学习stack友好，如果 c 是左括号字符 {, [, (，则将其对应的右括号字符 }，]，) 推入栈 stack 中，以便后续的匹配。
第一次写
class Solution { public static boolean isValid(String s) { if ("".equals(s)) return true; char[] chars = s.toCharArray(); Stack<Character> stack = new Stack<>(); boolean result = false; for (char c : chars) { switch (c) { case '{': stack.push('}'); break; case '[': stack.push(']'); break; case '(': stack.push(')'); break; case ')': case ']': case '}': if (stack.isEmpty()) return false; result = stack.pop() == c; //这里的操作有点繁琐了，后面要修改一下 尝试过return false也可以通过 if (!result) stack.push(c); break; default: return result; } } if (!stack.isEmpty()) { return false; } return result; } }
第二版，简化
class Solution { public static boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for (char c : s.toCharArray()) { if (c == '(' || c == '[' || c == '{') { stack.push(c); } else if (c == ')' || c == ']' || c == '}') { if (stack.isEmpty()) { return false; } char top = stack.pop(); if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) { return false; } } } return stack.isEmpty(); } }
网友Nakangzi，我觉得更好：
class Solution { public boolean isValid(String s) { Stack<Character>stack = new Stack<Character>(); for(char c: s.toCharArray()){ if(c=='(')stack.push(')'); else if(c=='[')stack.push(']'); else if(c=='{')stack.push('}'); else if(stack.isEmpty()||c!=stack.pop())return false; } return stack.isEmpty(); } }
官方还有栈+map的解法
注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回 FalseFalse，省去后续的遍历判断过程。
时间复杂度：O(n)
空间复杂度：O(n)
空间的占用来自与stack的大小，随着字符串的长度增加，stack占用的空间会变大。
