leetcode 20. 有效的括号

​
​

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
题目来源： leetcode官网
如果感觉博主的文章还不错的话，还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~

💜 题目描述

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

有效字符串需满足：

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

示例1：

输入：s = “()”
输出：true

示例2：

输入：s = “()[]{}”
输出：true

示例3：

输入：s = “(]”
输出：false

示例 4：

输入：s = “([)]”
输出：false

示例 5：

输入：s = “{[]}”
输出：true

🧡 算法分析

算法步骤:

1. 用栈存储， 拿出一个栈顶元素
2. 用栈顶元素和遍历得字符比较，可以枚举来匹配
3. 我们这里发现可以用ascii码比较来取消三对括号逐一进行匹配

💚 代码实现

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(auto c : s)
        {
            if (c == '(' || c == '[' || c == '{') st.push(c);
            else 
            {
                // 查ascii码表得，两个相对应得括号相差不超过2， 也可以用枚举对应法
                if(st.size() && abs(st.top() - c) <= 2) st.pop();
                else return false;
            }
        }
        return st.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

执行结果：

💙 时间复杂度分析

其中遍历一次， 时间复杂度为O(n)

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！