每天一算:Valid Parentheses

LeetCode上第20 号问题:有效的括号

题目

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

有效字符串需满足:

左括号必须用相同类型的右括号闭合。    
左括号必须以正确的顺序闭合。    
注意空字符串可被认为是有效字符串。

示例 1:

输入: “()”    
输出: true

示例 2:

输入: “()[]{}”  
输出: true

示例 3:

输入: “(]”  
输出: false

示例 4:

输入: “([)]”  
输出: false

示例 5:

输入: “{[]}”  
输出: true

解题思路

这道题让我们验证输入的字符串是否为括号字符串,包括大括号,中括号和小括号。

这里我们使用

  • 遍历输入字符串

  • 如果当前字符为左半边括号时,则将其压入栈中

  • 如果遇到右半边括号时,分类讨论:

  • 1)如栈不为空且为对应的左半边括号,则取出栈顶元素,继续循环  

  • 2)若此时栈为空,则直接返回false

  • 3)若不为对应的左半边括号,反之返回false

动画演示

动画演示GIF有点大,请稍微等待一下加载显示^_^


每天一算:Valid Parentheses


参考代码

每天一算:Valid Parentheses


每天一算:Valid Parentheses




我们会在每天早上8点30分准时推送一条LeetCode上的算法题目,并给出该题目的动画解析以及参考答案,每篇文章阅读时长为五分钟左右。

每天一算:Valid Parentheses
本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 每天一算:Valid Parentheses

我还会在以下平台发布内容

GitHub 哔哩哔哩