算法圖解：如何判斷括號是否有效？
本文轉載自微信公眾號「Java中文社群」，作者磊哥 。轉載本文請聯系Java中文社群公眾號。
今天要講的這道題是 bilibili 今年的筆試真題，也是一道關于棧的經典面試題。
經過前面文章的學習，我想很多朋友已經看出來了，我接下來要寫的是一個關于「算法圖解」的系列文章，中間可能會穿插少量的其他類型的文章，但「算法和數據結構」會是我今年文章輸出的重點內容。
我在寫這個算法系列的時候會注意兩個問題：
- 保證算法的解題思路大家都能看懂，因此我會以圖片的形式進行思路講解，這樣更直觀、更易于理解;
- 在介紹完一個知識點之后，會進行大量的練習，以鞏固所學的內容，比如當我講完「棧」結構之后，我會圍繞著「棧」做一系列的經典面試題練習。
學習算法最關鍵的是掌握解題的思路，只要思路對了，編寫代碼只是時間的問題。
那么接下來，我們就進入今天的正式內容...
題目
給定一個只包括 '('， ')'， '{'， '}'， '['， ']' 的字符串，判斷字符串是否有效。
有效字符串需滿足：
- 左括號必須用相同類型的右括號閉合。
- 左括號必須以正確的順序閉合。
- 注意空字符串可被認為是有效字符串。
示例 1:
- 輸入: "()"
- 輸出: true
示例 2:
- 輸入: "()[]{}"
- 輸出: true
示例 3:
- 輸入: "(]"
- 輸出: false
示例 4:
- 輸入: "([)]" 輸出: false
示例 5:
- 輸入: "{[]}"
- 輸出: true
- LeetCode 地址：https://leetcode-cn.com/problems/valid-parentheses
解題思路
這道題考察的是就是驗證括號的對稱性，比如“([{}])”這種字符串就是正確的，應該返回 true，而“([{})]”這種字符串就是錯誤的，應該返回 false。
從上面的題目可以看出，括號總共分為三類：小括號、中括號和大括號，那么我們可以利用棧先進后出的特性，將所有左邊的括號(“(”、“[”、“{”)先入棧，然后再碰到右括號時，讓它與棧頂的元素進行匹配，比如當遇到“)”時，如果棧頂是“(”，則說明匹配成功，棧頂元素出棧再繼續字符串循環的流程，如果匹配錯誤就直接返回 false。
假設我們要匹配字符串“(([]))”是否合法?那么執行流程就是這樣的。
首先遇到左邊括號，先入棧：
接下來又是左邊括號，繼續入棧：
然后又是左邊括號，繼續入棧：
接下來是右邊括號，與棧頂元素匹配，“[]”為一對合法的括號，匹配成功棧頂元素出棧：
接下來又是右邊括號，與棧頂元素匹配，“()”為一對合法的括號，匹配成功棧頂元素出棧：
接下來又是右邊括號，與棧頂元素匹配，“()”為一對合法的括號，匹配成功棧頂元素出棧：
當字符串循環結束并且棧為空棧時，則證明此字符串的括號匹配合法，最終的效果如下圖所示：
那么接下來我們就用代碼來實現一下整個過程...
實現代碼一
- public boolean isValid(String s) {
- int slen = s.length(); // 括號的長度
- if (slen % 2 == 1) { // 括號不是成對出現直接返回 false
- return false;
- }
- // 把所有對比的括號存入 map，對比時用
- Map<Character, Character> map = new HashMap<>();
- map.put(')', '(');
- map.put('}', '{');
- map.put(']', '[');
- // 定義棧，用于存取括號（輔助比較）
- Stack<Character> stack = new Stack<>();
- for (int i = 0; i < slen; i++) { // 循環所有字符
- char c = s.charAt(i);
- if (map.containsKey(c)) { // 為右邊的括號，如 ')'、'}' 等
- if (stack.isEmpty() || stack.peek() != map.get(c)) { // 棧為空或括號不匹配
- return false;
- }
- stack.pop(); // 是一對括號，執行出棧（消除左右括號）
- } else { // 左邊括號，直接入棧
- stack.push(c);
- }
- }
- return stack.isEmpty();
- }
我們在 LeetCode 中提交一下代碼，執行結果如下：
代碼解析
以上代碼的 map 集合是用于定義括號的匹配規則，比如“)”對應的匹配值是“(”，“]”的匹配值是“[”等，然后我們再去循環待驗證的字符串，遇到左括號直接入棧，遇到右括號讓它與棧頂元素匹配，等到整個字符串循環結束，如果棧為空則說明字符串的括號合法。
復雜度分析
時間復雜度：O(n)，遍歷了一遍整個字符串。空間復雜度：O(n)。
實現代碼二
除了使用棧之外，我們還可以使用借助 Java 中的 replace 方法來實現，我們可以循環的消除字符串中的括號，比如將“()”或“[]”或“{}”循環得替換為空，最后在執行完成之后如果字符串為空，則說明字符串中的括號是合法的，具體實現代碼如下：
- public boolean isValid(String s) {
- int len;
- do {
- len = s.length();
- // 消除成雙成對的符號
- s = s.replace("()", "").replace("[]", "").
- replace("{}", "");
- } while (len != s.length()); // 不能再進行替換了，replace 方法沒有替換任何字符
- return s.length() == 0;
- }
我們在 LeetCode 中提交一下代碼，執行結果如下：
從運行結果來看，二者的執行效率相差還是很明顯的：
總結
本文我們講了一道 bilibili 的筆試真題，同時它也是棧的經典面試題，我們可以借助棧的特性(先進后出)將所有的左括號入棧，當遇到右括號時讓它與棧頂元素進行匹配，當字符串循環結束棧為空時，則說明此字符串的括號是合法的。當然我們在實際面試中，也可以使用 Java 的 replace 方法作為一個保底的實現方案，因為replace 方法的實現相對更簡單一些，只是性能不怎么好。
