如何判断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有效的括号”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！