如何判斷LeetCode有效的括號

本篇內容介紹了“如何判斷LeetCode有效的括號”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

題目

有效的括號

描述

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

有效字符串需滿足：

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

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

示例 1：

輸入：s = "()"
輸出：true

示例 2：

輸入：s = "()[]{}"
輸出：true

示例 3：

輸入：s = "(]"
輸出：false

示例 4：

輸入：s = "([)]"
輸出：false

示例 5：

輸入：s = "{[]}"
輸出：true

Solution

解法

解題思路

判斷有效括號的思路有哪些？

• 如果s字符串的長度為奇數，則必不可能閉合，可以直接返回false

• 建立緩存映射，KEY為左括號，VALUE為右括號

• 通過利用棧 先入后出的特性非常適合我們這題的思路，如果遇到左括號（[({）入棧，在進行右括號（}])）判斷時將對應棧頂左括號出棧，最后遍歷完棧內數據為空

CODE

class Solution {
    public boolean isValid(String s) {
        int length  = s.length();
        //奇數則不可能閉合
        if(length%2==1){
            return false;
        }
      	//左括號與右括號的緩存映射
        Map<Character,Character> map = new HashMap<>();
        map.put('(',')');
        map.put('[',']');
        map.put('{','}');
        
        Stack<Character> stack = new Stack();
        for(int i = 0 ; i < length ; i++){
            char c =  s.charAt(i);
            //是否為左括號
            if(map.containsKey(c)){
                stack.push(c);
            }else{
              //如果是右括號，并且棧深為0，則說明當前的字符串為右括號的字符串，可直接返回false，如 ')'  '}'  ']'  '()())}]'
               if(stack.size()==0){
                   return false;
               }
              //彈出棧，并且從緩存中獲取，對應的右括號與當前字符串相匹配，是否相等，不相等則返回false
               if(!map.get(stack.pop()).equals(c)){
                   return false;
               }
            }
        }
      	//最終判斷棧深度，為空則說明對撐
        return stack.empty();
    }
}

復雜度

• 時間復雜度：O(n)，其中 n 是字符串 s 的長度

結果

• 執行用時：2 ms, 在所有 Java 提交中擊敗了76.91%的用戶

• 內存消耗：36.8 MB, 在所有 Java 提交中擊敗了25.12%的用戶

我曾在銀色平原漫步,也曾在青草之河垂釣，這片土地認識我，我們若不堅強，就將滅亡

“如何判斷LeetCode有效的括號”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！