两分钟看懂有效的括号

悠悠 2022-11-10 14:13 188阅读 0赞

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

![d47ace51870392b0f36adc18d7f028e5.png][]

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

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

有效字符串需满足：

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

**示例 1：**

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

**示例 2：**

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

**提示：**

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

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

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

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

**1.模拟**

有效的情况：

1）不嵌套

![b6ce02e55ccb2ab16ed0b71913fec668.png][]

2）嵌套

![d6194d37d6c2a40ccabb6cb1f0570335.png][]

无效的情况：

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

![eb28e97943c2097ae37acc164d89b10b.png][]

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

![8cdc3c95920f0e8dc88fcd94b53b6107.png][]

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

![a5d76150e6e80f090a1a046b974d418c.png][]

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

![f72859b353c3bb2ee7dce2ac645fecac.png][]

**2.规律**

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

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

**3.匹配**

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

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

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

![869a244438ac5139e2a78af8d6fc18fd.png][]

**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/

2、https://t10.lagounews.com/aR44RbR+c190C

[d47ace51870392b0f36adc18d7f028e5.png]: /images/20221022/161a3937af5944db9c2df0e8f8580ca9.png
[b6ce02e55ccb2ab16ed0b71913fec668.png]: https://img-blog.csdnimg.cn/img_convert/b6ce02e55ccb2ab16ed0b71913fec668.png
[d6194d37d6c2a40ccabb6cb1f0570335.png]: https://img-blog.csdnimg.cn/img_convert/d6194d37d6c2a40ccabb6cb1f0570335.png
[eb28e97943c2097ae37acc164d89b10b.png]: https://img-blog.csdnimg.cn/img_convert/eb28e97943c2097ae37acc164d89b10b.png
[8cdc3c95920f0e8dc88fcd94b53b6107.png]: https://img-blog.csdnimg.cn/img_convert/8cdc3c95920f0e8dc88fcd94b53b6107.png
[a5d76150e6e80f090a1a046b974d418c.png]: https://img-blog.csdnimg.cn/img_convert/a5d76150e6e80f090a1a046b974d418c.png
[f72859b353c3bb2ee7dce2ac645fecac.png]: https://img-blog.csdnimg.cn/img_convert/f72859b353c3bb2ee7dce2ac645fecac.png
[869a244438ac5139e2a78af8d6fc18fd.png]: https://img-blog.csdnimg.cn/img_convert/869a244438ac5139e2a78af8d6fc18fd.png