一、題目

二、解題思路

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的算法筆記》）