首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >要一遍做对——LeetCode题目20:有效的括号

要一遍做对——LeetCode题目20:有效的括号

作者头像
二环宇少
发布2020-08-13 15:36:59
发布2020-08-13 15:36:59
3150
举报

原题描述

+

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

有效字符串需满足:

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

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

示例 1

输入:"()"

输出:true

示例 2

输入:"()[]{}"

输出:true

示例 3

输入:"(]"

输出:false

示例 4

输入:"([)]"

输出:false

示例 5

输入:"{[]}"

输出:true

原题链接:https://leetcode-cn.com/problems/valid-parentheses

思路解析

+

即便是面试官有意放水,这道题还是有人做不对,因为心思不够缜密。知道用栈来判断有效性,但是不合法的条件有几种,你能一下想全吗?

  1. 当前扫描到右括号时,和栈顶不匹配;
  2. 当前扫描到右括号时,栈空了;
  3. 字符串扫描结束了,但是栈没有清空。

这道题现实中考的可能性很小,但自己还是做一做吧,就当一次娱乐了~

复杂度分析

+

  • 时间复杂度:
  • 空间复杂度:

C++参考代码

+

代码语言:javascript
复制
class Solution {
public:
    bool isValid(string s) {
        map<char, char> table = {
            {')', '('}, {']','['}, {'}','{'}
        };

        stack<char> my_stack;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
                my_stack.push(s[i]);
            } else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
                if (my_stack.size() == 0 || table[s[i]] != my_stack.top()) return false;
                else my_stack.pop();
            }
        }

        bool suc = my_stack.size() == 0 ? true: false;
        return suc;
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-06-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 互联网西门二少 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档