[[346613]]

本文轉(zhuǎn)載自微信公眾號「Java中文社群」，作者磊哥 。轉(zhuǎn)載本文請聯(lián)系Java中文社群公眾號。  

今天要講的這道題是 bilibili 今年的筆試真題，也是一道關(guān)于棧的經(jīng)典面試題。

經(jīng)過前面文章的學(xué)習(xí)，我想很多朋友已經(jīng)看出來了，我接下來要寫的是一個關(guān)于「算法圖解」的系列文章，中間可能會穿插少量的其他類型的文章，但「算法和數(shù)據(jù)結(jié)構(gòu)」會是我今年文章輸出的重點(diǎn)內(nèi)容。

我在寫這個算法系列的時候會注意兩個問題：

• 保證算法的解題思路大家都能看懂，因此我會以圖片的形式進(jìn)行思路講解，這樣更直觀、更易于理解;
• 在介紹完一個知識點(diǎn)之后，會進(jìn)行大量的練習(xí)，以鞏固所學(xué)的內(nèi)容，比如當(dāng)我講完「?！菇Y(jié)構(gòu)之后，我會圍繞著「?！棺鲆幌盗械慕?jīng)典面試題練習(xí)。

學(xué)習(xí)算法最關(guān)鍵的是掌握解題的思路，只要思路對了，編寫代碼只是時間的問題。

那么接下來，我們就進(jìn)入今天的正式內(nèi)容...

題目

給定一個只包括 '('， ')'， '{'， '}'， '['， ']' 的字符串，判斷字符串是否有效。

有效字符串需滿足：

• 左括號必須用相同類型的右括號閉合。
• 左括號必須以正確的順序閉合。
• 注意空字符串可被認(rèn)為是有效字符串。

示例 1:

輸入: "()" 
 
輸出: true 

示例 2:

輸入: "()[]{}" 
 
輸出: true 

示例 3:

輸入: "(]" 
輸出: false 

示例 4:

輸入: "([)]" 輸出: false 

示例 5:

輸入: "{[]}" 
輸出: true 
LeetCode 地址：https://leetcode-cn.com/problems/valid-parentheses 

解題思路

這道題考察的是就是驗(yàn)證括號的對稱性，比如“([{}])”這種字符串就是正確的，應(yīng)該返回 true，而“([{})]”這種字符串就是錯誤的，應(yīng)該返回 false。

從上面的題目可以看出，括號總共分為三類：小括號、中括號和大括號，那么我們可以利用棧先進(jìn)后出的特性，將所有左邊的括號(“(”、“[”、“{”)先入棧，然后再碰到右括號時，讓它與棧頂?shù)脑剡M(jìn)行匹配，比如當(dāng)遇到“)”時，如果棧頂是“(”，則說明匹配成功，棧頂元素出棧再繼續(xù)字符串循環(huán)的流程，如果匹配錯誤就直接返回 false。

假設(shè)我們要匹配字符串“(([]))”是否合法?那么執(zhí)行流程就是這樣的。

首先遇到左邊括號，先入棧：

接下來又是左邊括號，繼續(xù)入棧：

然后又是左邊括號，繼續(xù)入棧：

接下來是右邊括號，與棧頂元素匹配，“[]”為一對合法的括號，匹配成功棧頂元素出棧：

接下來又是右邊括號，與棧頂元素匹配，“()”為一對合法的括號，匹配成功棧頂元素出棧：

接下來又是右邊括號，與棧頂元素匹配，“()”為一對合法的括號，匹配成功棧頂元素出棧：

當(dāng)字符串循環(huán)結(jié)束并且棧為空棧時，則證明此字符串的括號匹配合法，最終的效果如下圖所示：

那么接下來我們就用代碼來實(shí)現(xiàn)一下整個過程...

實(shí)現(xiàn)代碼一

public boolean isValid(String s) { 
    int slen = s.length(); // 括號的長度 
    if (slen % 2 == 1) { // 括號不是成對出現(xiàn)直接返回 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++) { // 循環(huán)所有字符 
        char c = s.charAt(i); 
        if (map.containsKey(c)) { // 為右邊的括號，如 ')'、'}' 等 
            if (stack.isEmpty() || stack.peek() != map.get(c)) { // 棧為空或括號不匹配 
                return false; 
            } 
            stack.pop(); // 是一對括號，執(zhí)行出棧（消除左右括號） 
        } else { // 左邊括號，直接入棧 
            stack.push(c); 
        } 
    } 
    return stack.isEmpty(); 
} 

我們在 LeetCode 中提交一下代碼，執(zhí)行結(jié)果如下：

代碼解析

以上代碼的 map 集合是用于定義括號的匹配規(guī)則，比如“)”對應(yīng)的匹配值是“(”，“]”的匹配值是“[”等，然后我們再去循環(huán)待驗(yàn)證的字符串，遇到左括號直接入棧，遇到右括號讓它與棧頂元素匹配，等到整個字符串循環(huán)結(jié)束，如果棧為空則說明字符串的括號合法。

復(fù)雜度分析

時間復(fù)雜度：O(n)，遍歷了一遍整個字符串。空間復(fù)雜度：O(n)。

實(shí)現(xiàn)代碼二

除了使用棧之外，我們還可以使用借助 Java 中的 replace 方法來實(shí)現(xiàn)，我們可以循環(huán)的消除字符串中的括號，比如將“()”或“[]”或“{}”循環(huán)得替換為空，最后在執(zhí)行完成之后如果字符串為空，則說明字符串中的括號是合法的，具體實(shí)現(xiàn)代碼如下：

public boolean isValid(String s) { 
        int len; 
        do { 
            len = s.length(); 
            // 消除成雙成對的符號 
            s = s.replace("()", "").replace("[]", ""). 
                    replace("{}", ""); 
        } while (len != s.length()); // 不能再進(jìn)行替換了，replace 方法沒有替換任何字符 
        return s.length() == 0; 
    } 

我們在 LeetCode 中提交一下代碼，執(zhí)行結(jié)果如下：

從運(yùn)行結(jié)果來看，二者的執(zhí)行效率相差還是很明顯的：

總結(jié)

本文我們講了一道 bilibili 的筆試真題，同時它也是棧的經(jīng)典面試題，我們可以借助棧的特性(先進(jìn)后出)將所有的左括號入棧，當(dāng)遇到右括號時讓它與棧頂元素進(jìn)行匹配，當(dāng)字符串循環(huán)結(jié)束棧為空時，則說明此字符串的括號是合法的。當(dāng)然我們在實(shí)際面試中，也可以使用 Java 的 replace 方法作為一個保底的實(shí)現(xiàn)方案，因?yàn)閞eplace 方法的實(shí)現(xiàn)相對更簡單一些，只是性能不怎么好。