☆打卡算法☆LeetCode 20、有效的括号 算法解析

举报
恬静的小魔龙 发表于 2021/10/24 18:14:04 2021/10/24
【摘要】 推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。 一、题目 1、算法题目“给定一个字符串,判断字符串是否包含有效的括号。”题目链接:来源:力扣(LeetCode)链接:20. 有效的括号 - 力扣(Le...

推荐阅读

大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个字符串,判断字符串是否包含有效的括号。”

题目链接:

来源:力扣(LeetCode)

链接:20. 有效的括号 - 力扣(LeetCode) (leetcode-cn.com)

2、题目描述

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

有效字符串需满足:

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
示例 1:
输入: s = "()"
输出: true
示例 2:
输入: s = "{[]}"
输出: true
示例 3:
输入: s = "([)]"
输出: false

二、解题

1、思路分析

这道题,判断括号的有效性,可以使用栈来解决。

在遍历字符串的时候,如果遇到一个左括号时,会期望在后面的遍历时,有一个相同类型的右括号进行闭合,所以可以将这个左括号放入栈顶。

当遇到一个右括号的时候,取出栈顶的左括号进行判断是否是相同类型的括号,如果不是返回false。

遍历结束,栈中没有左括号,说明字符串左括号闭合,返回true,否则返回false。

2、代码实现

采用栈方法解题,将括号存入字典键值对,出栈判断与字典值是否相等,代码参考:

public class Solution {
    public bool IsValid(string s) {
        if (s == "" || s == null) return false;
        // 反着的原因是,进入栈的值必须为左边括号,这样可以判断出栈的值与当前dic的值是否相等
        Dictionary<char, char> dic = new Dictionary<char, char>{{ ']', '[' }, { ')', '(' }, { '}', '{' }};
        var stack = new Stack<char>();
        foreach (var c in s)
        {
            if (dic.ContainsKey(c))
            {
                // 栈为空时说明第一个字符为右括号
                if (stack.Count == 0) return false;
                // 出栈的值与当前dic的值不相等就返回 false
                if (stack.Pop() != dic[c]) return false;
            }
            else
                stack.Push(c);
        }
        return stack.Count == 0 ? true : false;
    }
}

image.png

3、时间复杂度

时间复杂度 : O(n)

其中n是字符串的长度

空间复杂度: O(n+∣Σ∣),其中 \SigmaΣ 表示字符集,本题中字符串只包含 66 种括号,∣Σ∣=6。栈中的字符数量为 O(n),而哈希表使用的空间为 O(∣Σ∣),相加即可得到总空间复杂度。

三、总结

注意到有效字符串的长度一定为偶数,因此如果字符串的长度为奇数,我们可以直接返回 False,省去后续的遍历判断过程。

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

评论(0

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

全部回复

上滑加载中

设置昵称

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

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

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

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