LeetCode力扣每日一题（Java）：20、有效的括号

一、题目

二、解题思路

1、我的思路

我看到题目之后，想着这可能是力扣里唯一一道我能秒杀的题目了

于是一波操作猛如虎写出了如下代码

public boolean isValid(String s) {char[] c = s.toCharArray();for(int i=0;i<c.length;i++){switch (c[i]){case '(':if(c[++i]!=')')return false;break;case '[':if(c[++i]!=']')return false;break;case '{':if(c[++i]!='}')return false;break;}}return true;}

运行的时候三个测试用例都通过了，我心想这把稳了。信心满满地点击提交……

什么？！解答错误

嗷，那没事了，原来左括号后不一定跟的是右括号……这就回去重写

再仔细一思考，猛然回想起当时学数据结构的时候遇到过的括号匹配问题。这可能要用到栈，遇到左括号就让这个左括号进栈，遇到右括号就出栈一个括号，如果这两个括号能匹配就继续执行，反之则直接返回false

于是有了如下的代码，而且这段代码的运行效率竟然击败了98%的用户

char[] sc = s.toCharArray();Stack<Character> stack = new Stack<>();for(int i=0;i<sc.length;i++){switch (sc[i]){case '(':case '{':case '[':stack.push(sc[i]);break;default:if(stack.size()==0){return false;}switch(stack.pop()){case '(':if(sc[i]!=')')return false;break;case '{':if(sc[i]!='}')return false;break;case '[':if(sc[i]!=']')return false;break;}}}if(stack.size()!=0){return false;}return true;

 只不过我一开始没有考虑到循环中的

if(stack.size()==0){return false;
}

和循环结束的

if(stack.size()!=0){return false;
}

导致代码在测试 "[" 和 "]" 两个测试用例的时候都返回了错误的结果，还好力扣上可以看到出错的执行用例，所以我才能很快地找到问题

但是有很多算法竞赛是看不到执行出错的测试用例的，所以在打算法竞赛时，如果我们提交的代码出现了问题，不妨自己输入一些数据进行测试，而且要输入比较特殊的例子，如 "[" 和 "]" 这样的极端例子

2、官方题解

class Solution {public boolean isValid(String s) {int n = s.length();if (n % 2 == 1) {return false;}Map<Character, Character> pairs = new HashMap<Character, Character>() {{put(')', '(');put(']', '[');put('}', '{');}};Deque<Character> stack = new LinkedList<Character>();for (int i = 0; i < n; i++) {char ch = s.charAt(i);if (pairs.containsKey(ch)) {if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {return false;}stack.pop();} else {stack.push(ch);}}return stack.isEmpty();}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/valid-parentheses/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

三、栈

考虑到可能也有一些小伙伴不会用栈，在这里给大家科普一下（图片来源于《labuladong的算法笔记》）