LeetCode 20. 有效的括号（栈、字符串）

矫情吗；* 2022-11-28 10:45 119阅读 0赞

**上一篇博客：[LeetCode 14.最长公共前缀（字符串）][LeetCode 14.]**

>  写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。最近萌生了刷LeetCode的想法，所以我打算从LeetCode简单的题目开始做起，攻陷LeetCode。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[LeetCode 20. 有效的括号  
][LeetCode 20. _]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  示例
     *   *  示例 1
         *  示例 2
         *  示例 3
         *  示例 4
         *  示例 5
 *  题解
 *   *  解题思路
     *  解题代码
     *  时间复杂度
     *  提交情况

# 题目信息 #

## 题目描述 ##

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

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

## 示例 ##

### 示例 1 ###

> 输入: “()”  
> 输出: true

### 示例 2 ###

> 输入: “()\[\]\{\}”  
> 输出: true

### 示例 3 ###

> 输入: “(\]”  
> 输出: false

### 示例 4 ###

> 输入: “(\[)\]”  
> 输出: false

### 示例 5 ###

> 输入: “\{\[\]\}”  
> 输出: true

# 题解 #

## 解题思路 ##

我们可以使用数据结构中的`栈`来解决这个题目。首先我们判断一下字符串 **s** 是否为空，因为题目说了空字符串可被认为是有效字符串，所以只要一开始 **s** 为空那么我们就直接 `return true;`即可。

当 **s** 不为空的时候我们就开始依次遍历字符串 **s** 如果遇到 `左括号` 那么我们就将其 **入栈** 否则就判断一下当前的栈是否为空如果为空说明第一个就是 **右括号** 此时我们直接 `return false;`即可。如果此时栈不为空，那么我们继续判断栈顶的 **左括号** 是否成功匹配到了 **右括号**，如果成功匹配到了那么我们就将当前栈顶的左括号 **出栈**，没有成功匹配到就直接`return false;`。

最后我们再判断一下栈是否为空，如果栈为空，说明 **s** 中的所有括号均有效，此时`return true;`即可。不为空说明有的 **右括号** 缺少对应的 **左括号**，此时`return false;`即可。  
![图解1][1]  
![题解2][2]

## 解题代码 ##

class Solution { 
    public:
        bool isValid(string s) { 
            stack<char> stk;
            if (s.empty()) return true;
            for (int i = 0; i < s.size(); i++) { 
                if (s[i] == '(' || s[i] == '{' || s[i] == '[') { 
                    stk.push(s[i]);
                } else { 
                    if (!stk.empty() && ((stk.top() == '(' && s[i] == ')') || (stk.top() == '{' && s[i] == '}') || (stk.top() == '[' && s[i] == ']'))) { 
                        stk.pop();
                    } else { 
                        return false;
                    }
                }
            }
            if (stk.empty()) return true;
            return false;
        }
    };

## 时间复杂度 ##

>  时间复杂度：**O(n)**，其中 **n** 是字符串 **s** 的长度。

## 提交情况 ##

![提交情况][2020081713380856.png]

--------------------

> 未完待续，持续更新中……  
> ![冲鸭！][20200817133931518.png]

[LeetCode 14.]: https://ac-fun.blog.csdn.net/article/details/108035699
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[LeetCode 20. _]: https://leetcode-cn.com/problems/valid-parentheses/
[1]: /images/20221124/c1be9b2120064d18a6fd9e0694f488c7.png
[2]: /images/20221124/70006ecc15834f1191df8bc2905bd6f1.png
[2020081713380856.png]: /images/20221124/bcb0e32f42594260968c8c436d30e308.png
[20200817133931518.png]: /images/20221124/ed478e7a6e804d259fffa6f846b18225.png