怎么判斷括號是否有效

本篇內容主要講解“怎么判斷括號是否有效”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“怎么判斷括號是否有效”吧!

題目

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

有效字符串需滿足：

• 左括號必須用相同類型的右括號閉合。

• 左括號必須以正確的順序閉合。

• 注意空字符串可被認為是有效字符串。

示例 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 中提交一下代碼，執行結果如下：

從運行結果來看，二者的執行效率相差還是很明顯的：

到此，相信大家對“怎么判斷括號是否有效”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！