题目描述
- 给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
- 有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
练习地址
实现
- 实现
- 98.41% 解法
- 思路
时间复杂度 O(N)：正确的括号组合需要遍历 11 遍 s；
空间复杂度 O(N)：哈希表和栈使用线性的空间大小。
思路 - 代码
public boolean isValid(String s) {if(s.isEmpty())return true;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.empty()||c!=stack.pop())return false;}if(stack.empty())return true;return false;}
- 实现 78.37%
class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<Character>();for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);if (ch == '(' || ch == '[' || ch == '{') {switch (ch) {case '(':stack.push(ch);break;case '[':stack.push(ch);break;case '{':stack.push(ch);break;}}if (ch == ')' || ch == ']' || ch == '}') {if(stack.size() > 0 && stack != null){char ch2 = stack.peek();switch (ch) {case ')':if (ch2 == '('){stack.pop();}else{return false;}break;case ']':if (ch2 == '['){stack.pop();}else{return false;}break;case '}':if (ch2 == '{'){stack.pop();}else{return false;}break;}}else{return false;}}}if (stack.size() == 0) {return true;}return false;}}