有效的括号

举报
Linux猿 发表于 2021/10/24 22:06:08 2021/10/24
【摘要】 🎈 作者:Linux猿 🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、面试、刷题、算法尽管咨询我,关注我,有问题私聊! 🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

🎈 作者:Linux猿

🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、面试、刷题、算法尽管咨询我,关注我,有问题私聊!

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬


一、题目描述
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否全部配对。 即: 左括号必须用相同类型的右括号闭合,左括号必须以正确的顺序闭合。

其中:

1 <= s.length <= 10^4;

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

二、题目样例
输入:s = "()[]{}"

输出:true

说明:上面的左右括号都能配对成功。

三、算法思路
本题是一个非常不错的栈应用例子,使用栈作为辅助数据结构,依次遍历字符串 s,步骤如下所示:

1. 如果是左括号,例如:(,{,[,则进栈;

2. 如果是右括号,例如:),},],则首先查看栈顶元素;

3. 如果没有栈顶元素,即栈已空,则括号不匹配;

4. 如果有栈顶元素,则查看栈顶是否与当前元素相匹配的左括号,是则删除栈顶元素,否则括号不匹配。

5. 一直循环 1 ~ 4,直到遍历完字符串 s;

6. 如果栈中最后还有元素,说明括号不匹配,否则,括号匹配。        

四、代码实现
4.1 头文件

#include <iostream>
#include <stack>
#include <map>
using namespace std;

4.2 具体代码

class Solution {
public:
    bool isValid(string s) {
        if(s.size() % 2) return false;  // 判断是否成对,不成对则直接返回 false
        stack<char>st;  // 栈
        map<char, char>brt = { // 配置成对括号
            {'(', ')'},
            {'{', '}'},
            {'[', ']'}
        };
        for(int i = 0; i < s.size(); ++i) {
            if(brt.count(s[i])) { // 判断是否是左括号
                st.push(s[i]);
            } else if(!st.empty() && brt[st.top()] == s[i]){ // 如果是右括号,判断是否是与栈顶括号配对
                st.pop();
            } else { // 前两种条件都不符合的话,则返回 false
                return false;
            }
        }
        return st.empty(); // 最后如果还有没配置的括号,则返回 false,否则 true
    }
};

五、题目链接

力扣

六、总结

本题考查栈的应用,是一个非常经典的题型,遍历的时候注意判断栈是否为空,最后也需要注意判断栈是否为空。


CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、面试、刷题、算法尽管咨询我,关注我,有问题私聊!

欢迎小伙伴们点赞👍、收藏⭐、留言💬


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200