图解LeetCode20：有效的括号（栈结构解法）

Bertha 。 2023-10-04 17:24 2阅读 0赞

### LeetCode20：有效的括号 ###

#### 内容目录 ####

*   *  LeetCode20：有效的括号
     *   *  一、解题思路
         *  二、代码实现
         *  三、代码执行情况

给定一个只包括 ‘(’，’)’，’\{’，’\}’，’\[’，’\]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。  
左括号必须以正确的顺序闭合。

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

提示：

1 <= s.length <= 104  
s 仅由括号 ‘()\[\]\{\}’ 组成  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16]

#### 一、解题思路 ####

由题目可以看出来，这种题目就是一个近邻匹配的问题。在出现一个右边括号时，紧接着应该有一个左边括号，需要从外向内匹配

因为如果有一个右括号，则需要和最近的左括号进行匹配，根据栈的先进后出特点，刚好匹配，可以引入栈的理念。具体步骤如图  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16 1]

**注意：**

在这里有几个注意事项，在取出栈中元素进行匹配的时候，需要判断栈是否为空，如果为空，就返回false，防止空指针异常

比如对于一个字符串"\]\]\]\]\]\]"，这时候去栈中匹配，因为第一个就是右括号，所以他是没有元素的

#### 二、代码实现 ####

在匹配的时候，可以实例一个map，key为右括号，value为左括号

HashMap<Character, Character> map = new HashMap<Character, Character>() {
        {
        
        put(')', '(');
        put(']', '[');
        put('}', '{');
    }};

总体代码实现

public boolean isValid(String s){
        
    
        int len = s.length();
        // 如果长度为奇数，一定为零
        if (len%2 == 1) return false;
        // 实例化一个map，存放括号
        HashMap<Character, Character> map = new HashMap<Character, Character>() {
        {
        
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        // 实例化一个栈结构
        Deque<Character> stack = new LinkedList<>();
    
        // 遍历字符串
        for (int i = 0; i < len; 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();
    
    }

#### 三、代码执行情况 ####

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16 2]

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/2e426e4973d24799a5d63391c704c100.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54mn56CB5paH,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/e1b1f95e925941ad9950e176954e4744.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54mn56CB5paH,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/d8f30fcc52534755ab0b802ecdde4ca4.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54mn56CB5paH,size_20,color_FFFFFF,t_70,g_se,x_16