【刷题记录】20. 有效的括号
一、题目描述
来源:力扣(LeetCode)
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1:
复制代码
示例 2:
复制代码
示例 3:
复制代码
示例 4:
复制代码
示例 5:
复制代码
提示:
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
二丶思路分析
使用栈来解决
在这道题目中,我们遍历时候,每个左括号,都要对应一个相应的右括号,而且后面出现的左括号要优先匹配,这个跟栈 先进后出
是十分类似的。
当遇到左括号时候,入栈
当遇到右括号时候,取出栈顶括号
判断出去括号 是否跟右括号类型一致,不一致,直接返回
false
如果栈中没有左括号了,也直接返回
false
当遍历完所有的字符串
栈为空,说明所有的括号都闭合了
栈不为空,说明还有括号没有匹配闭合
当匹配的时候,字符串长度一定为偶数,否则肯定不匹配,直接返回
false
为了方便匹配,我们可以用哈希表存储每一种括号。键为右括号,值为相同类型的左括号。
三、代码实现
复制代码
复杂度分析
时间复杂度:,其中 n
是字符串 s
的长度。
空间复杂度:复杂度为 ,使用哈希表的空间
运行结果
总结
有些问题,我们可以使用有类似特性的数据结构来处理,可以帮我们更快的解决问题。
版权声明: 本文为 InfoQ 作者【WangNing】的原创文章。
原文链接:【http://xie.infoq.cn/article/4e5fcc80cad264833aa56e060】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论