三分钟基础之栈训练：有效括号匹配-技术圈

往期回顾

三分钟基础：什么是时间｜空间复杂度

三分钟基础：什么是数组

三分钟基础：什么是链表

今天来判断括号是否有效，常见题。

不知道说啥，开整吧。

LeetCode 20：有效的括号

题意

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

示例

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

输出：true

输入：s = "([)]"

输出：false

提示

有效字符串需满足：

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

1 <= s.length <= 10^4

s 仅由括号 () [] {} 组成

题目解析

括号匹配是使用栈解决的经典问题，难度简单。

还不太会的臭宝看下面链接，本蛋写的：

呔！“栈”住，队列！

看会了栈，这道题基本就会了大半，剩下小半就是动动小脑袋瓜，稍微思考。

这题就是维护一个栈，碰到左括号就入栈，碰到右括号，取出栈顶元素，判断栈顶元素和右括号是否匹配。

如果不匹配，返回 false，如果匹配则重复上述步骤，直到遍历完字符串。

需要注意的是，有两种特殊情况也是返回 false：

遍历完整个字符串，栈不为空，说明多了左括号。
碰到右括号，但此时栈为空，说明多了右括号。

抛除上面的情况，其余的都返回 true。

图解

假设 s = "()[]{}"

首先初始化。

# 初始化stack = []
pairs = {    ')': '(',    ']': '[',    '}': '{'}

根据“题目解析”中说的，碰到左括号入栈，所以第 1 步，"(" 入栈

for i in s:    # 如果是左括号，压入栈    if i not in pairs:        stack.append(i)

接下来碰到右括号 ")"，取出栈顶元素 "("，判断栈顶元素是否和当前右括号配对，结果发现配对。

既然匹配，那就继续进行下 1 步，接下来碰到左括号 "["，入栈。

接下来碰到右括号 "]"，取出栈顶元素 "["，判断栈顶元素是否和当前右括号配对，结果发现配对。

既然又匹配，那就继续进行下 1 步，接下来碰到左括号 "{"，入栈。

接下来碰到右括号 "}"，取出栈顶元素 "{"，判断栈顶元素是否和当前右括号配对，结果发现配对。

此时字符串全部遍历完，同时栈也为空，字符串 s 有效，返回 true。

 return not stack

再来假设 s = "([)]"

前两个元素都是左括号，所以直接入栈。

啥接下来碰到右括号 ")"，取出栈顶元素 "["，栈顶元素与右括号不匹配，返回 false。

# 在遍历过程中，碰到空栈或者括号不匹配，返回 False。elif not stack or pairs[i] != stack.pop():    return False

每个元素的进栈或出栈的操作都是 O(1)，最坏情况下，每个元素都会进且仅进栈 1 次，所以时间复杂度为 O(1) * n = O(n)。

同理，最坏情况下，是所有的元素都入栈，所以空间复杂度也为 O(n)。

代码实现

Python 代码实现

class Solution:    def isValid(self, s: str) -> bool:
        # 字符串有奇数个元素，不匹配        if len(s) % 2 == 1:            return False
        # 初始化栈        stack = []
        pairs = {            ')': '(',            ']': '[',            '}': '{'        }
        for i in s:            # 如果是左括号，压入栈            if i not in pairs:                stack.append(i)            # 在遍历过程中，碰到空栈或者括号不匹配，返回 False。            elif not stack or pairs[i] != stack.pop():                return False
        # 全部遍历完，如果栈为空，返回 True，栈不为空，返回 False        return not stack

Java 代码实现

class Solution {    public boolean isValid(String s) {        Deque<Character> deque = new LinkedList<>();        char ch;        for (int i = 0; i < s.length(); i++) {            ch = s.charAt(i);            //碰到左括号，就把相应的右括号入栈            if (ch == '(') {                deque.push(')');            }else if (ch == '{') {                deque.push('}');            }else if (ch == '[') {                deque.push(']');            } else if (deque.isEmpty() || deque.peek() != ch) {                return false;            }else {//如果是右括号判断是否和栈顶元素匹配                deque.pop();            }        }        //最后判断栈中元素是否匹配        return deque.isEmpty();    }}

图解有效的括号到这里就结束啦。

栈的实战第一道题，题目比较简单，写写画画仔细思考一定没问题哒。

最后，推荐一波帅地的知识星球，欢迎热爱学习的萌新来玩耍(阅读原文里还有优惠卷哦)

一个专注于校招/在校生成长的社群，这里有项目资料，大牛分享，简历修改，一对一问答服务，你有什么困惑，帅地都会详细解答你，绝对物所超值，详情可以点击阅读原文了解哦(原文里有优惠卷)