LeetCode 20. 有效的括号（超详细超容易理解的动画解法！！！）

﹏ヽ暗。殇╰゛Y 2022-11-11 14:55 26阅读 0赞

大家好，我是程序员吴师兄，今天跟大家分享一道和 **栈** 有关的题目，超级简单也超级容易理解，这道题目曾经出现在 bilibili 的面试中。

![v2-7ebb85dc84719c2053f5301383e16396\_b.jpg][v2-7ebb85dc84719c2053f5301383e16396_b.jpg]

### 一、题目描述 ###

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

有效字符串需满足：

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

**示例 1：**

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

**示例 2：**

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

**提示：**

*  1 <= s.length <= 104
 *  s 仅由括号 '()\[\]\{\}' 组成

### 二、题目解析 ###

我们用 **四步分析法** 来分析一下这道题目。

*  模拟：模拟题目的运行。  
    
 *  规律：尝试总结出题目的一般规律和特点。  
    
 *  匹配：找到符合这些特点的数据结构与算法。  
    
 *  边界：考虑特殊情况。

**1.模拟**

有效的情况：

1）不嵌套

![v2-e1f3407b146809ab79b6c4f2242b11ee\_b.jpg][v2-e1f3407b146809ab79b6c4f2242b11ee_b.jpg]

2）嵌套

![v2-eea0c711123cf56874ef083c786b7020\_b.jpg][v2-eea0c711123cf56874ef083c786b7020_b.jpg]

无效的情况：

1）长度为奇数，左括号多余

![v2-c1bba40e3df6be030b0d5ddcaf70c949\_b.jpg][v2-c1bba40e3df6be030b0d5ddcaf70c949_b.jpg]

2）长度为奇数，右括号多余

![v2-66c8589cca6dd695f8df84076c1f66c2\_b.jpg][v2-66c8589cca6dd695f8df84076c1f66c2_b.jpg]

3）长度为偶数，左括号与右括号不配对

![v2-d22c4f8b0e2d51820fec4771d167d8ae\_b.jpg][v2-d22c4f8b0e2d51820fec4771d167d8ae_b.jpg]

4）长度为偶数，部分子表达式可以配对，但外部不配对

![v2-d975693cd6e3b2029cc6ff3d8fac1e0d\_b.jpg][v2-d975693cd6e3b2029cc6ff3d8fac1e0d_b.jpg]

**2.规律**

通过上述的模拟，可以总结出以下 3 个特点：

*  1、**(** 与 **）**、**\[** 与 **\]**、**\{**  与 **\}** 是一一对应的关系，无法**配对**是无效的
 *  2、对于有效的括号，它的部分子表达式仍然是有效的括号，比如 **\{ \[ ( ) \]\}** ，如果部分子表达式无效，那么整体都是无效的
 *  3、部分子表达式如果建立了配对关系，是有效的括号，那么 **消除** 后是不会影响整体的
 *  4、奇数长度的字符串总是无效的。

**3.匹配**

整个过程分为两步，一个是配对，一个是消除。

**配对** 过程，**（** 与 **）**、**\[** 与 **\]**、**\{**  与 **\}**。

**消除** 的过程是**由内向外**进行，先判断能否消除部分子表达式（内），再判断能否消除整体表达式（外），但在遍历的过程却是**由外向内**进行遍历，需要保存状态，**栈** 先进后出的特点符合要求。

![v2-72c42a4fdba59986e31d659c807eeef5\_b.jpg][v2-72c42a4fdba59986e31d659c807eeef5_b.jpg]

**4.边界**

所谓边界，即特殊情况：

*  字符串的长度为奇数

### 三、动画图解 ###

### 四、参考代码 ###

// 登录 https://www.algomooc.com 查看更多图解
    class Solution {
          
    
        public boolean isValid(String s) {
          
            // 当字符串长度为奇数的时候，属于无效情况
            // 条件说明了长度至少为 1，所以不需要在判空
                if (s.length() % 2 == 1) {
          
                   return false;
            }
    
              //构建栈
            Stack<Character> stack = new Stack<Character>();
    
            //由外向内遍历字符串
            for(char c : s.toCharArray()){
          
    
                if(c == '('){
          
                   stack.push(')');
                }else if(c == '['){
          
                   stack.push(']');
                }else if( c == '{'){
          
                   stack.push('}');
                }else if( stack.isEmpty() || c != stack.pop()){
          
                //表明有多余的括号
                   return false;
                }
            }
            return stack.isEmpty();
        }
    }

### 五、复杂度分析 ###

### 时间复杂度 ###

时间复杂度为 O(N)。需要遍历一遍字符串。

### 空间复杂度 ###

空间复杂度 O(N)。哈希表和栈使用线性的空间大小，最坏情况下，栈的大小将是输入字符串的长度。

### 六、参考引用 ###

1、[https://leetcode-cn.com/problems/valid-parentheses/solution/valid-parentheses-fu-zhu-zhan-fa-by-jin407891080/][https_leetcode-cn.com_problems_valid-parentheses_solution_valid-parentheses-fu-zhu-zhan-fa-by-jin407891080]

2、[https://t10.lagounews.com/aR44RbR+c190C][https_t10.lagounews.com_aR44RbR_c190C]

[v2-7ebb85dc84719c2053f5301383e16396_b.jpg]: /images/20221022/a75300a430aa4570a6698cdf6761d29a.png
[v2-e1f3407b146809ab79b6c4f2242b11ee_b.jpg]: /images/20221022/b778186457774a719b7d883b7a513918.png
[v2-eea0c711123cf56874ef083c786b7020_b.jpg]: /images/20221022/82ef3f9c20954c9cb6acfa6369047cd2.png
[v2-c1bba40e3df6be030b0d5ddcaf70c949_b.jpg]: /images/20221022/37fb429daf7c4f05ab2574945a27d420.png
[v2-66c8589cca6dd695f8df84076c1f66c2_b.jpg]: https://img-blog.csdnimg.cn/img_convert/c10618138f9e10efb2bdf4c21a6f81c7.png
[v2-d22c4f8b0e2d51820fec4771d167d8ae_b.jpg]: https://img-blog.csdnimg.cn/img_convert/3e6616f8196f13d4fa370acdc73d1c91.png
[v2-d975693cd6e3b2029cc6ff3d8fac1e0d_b.jpg]: https://img-blog.csdnimg.cn/img_convert/b785392224717f0ddb48848a720de401.png
[v2-72c42a4fdba59986e31d659c807eeef5_b.jpg]: https://img-blog.csdnimg.cn/img_convert/1d2f0ffbf35aada1bc82cfef0808c6a9.png
[https_leetcode-cn.com_problems_valid-parentheses_solution_valid-parentheses-fu-zhu-zhan-fa-by-jin407891080]: https://link.zhihu.com/?target=https%3A//leetcode-cn.com/problems/valid-parentheses/solution/valid-parentheses-fu-zhu-zhan-fa-by-jin407891080/
[https_t10.lagounews.com_aR44RbR_c190C]: https://link.zhihu.com/?target=https%3A//t10.lagounews.com/aR44RbR%2Bc190C