题目:
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占用的空间会变大。