【牛客-算法】NC52 有效括号序列

Java光头强 • 2023年2月20日上午8:50 • 后端漫谈 • 阅读 224

文章目录

🚩 写在前面
1.题目描述
2.算法设计思路
3.算法实现（C++）
4.运行结果
结束语：

🚩 写在前面

🔥 该专栏作为算法题笔记，记录算法的思路、遇到的问题，以及能跑的代码，持续更新中！
🔥 推荐一款面试、刷题神器牛客网：👉开始刷题学习👈

1.题目描述

描述
给出一个仅包含字符’(’,’)’,’{’,’}’,’[‘和’]’,的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，”()“和”()[]{}“都是合法的括号序列，但”(]“和”([)]”不合法。

数据范围：字符串长度

≤

10000

0\le n \le 10000

$0 \leq n \leq 10000$
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

2.算法设计思路

使用栈可以很方便地解决这个问题。下面是算法过程描述：

每次从字符串读取一个括号
与栈顶括号进行比较
- 若匹配，则将栈顶括号出栈
- 若不匹配，则将读取到的括号压入栈
直到字符串为空时，检查栈是否为空。
- 若栈空，则说明字符串是合法的括号序列；
- 若栈不为空，那么字符串是不合法的括号序列。

来张草图:

3.算法实现（C++）

#include<stack>
class Solution {
public:
    /**
     * @param s string字符串 
     * @return bool布尔型
     */
    bool match(char a, char b){
        //判断ab是否为匹配的括号
        if(a == '(' && b == ')'){
            return true;
        }else if(a == '[' && b == ']'){
            return true;
        }else if(a == '{' && b == '}'){
            return true;
        }
        return false;
    }
    bool isValid(string s) {
        // write code here
        stack<char> sta;
        for(int i = 0; s[i] != '\0'; i++){
            if(!sta.empty() && match(sta.top(), s[i])){
                sta.pop();
            }else{
                sta.push(s[i]);
            }
        }
        if(sta.empty()){
            return true;
        }
        return false;
    }
};