题目
给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s
判断字符串是否有效
有效字符串需满足:
1.左括号必须用相同类型的右括号闭合
2.左括号必须以正确的顺序闭合
规则示例
规则:
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成
示例 1:
输入:s = “()”
输出:true
示例 2:
输入:s = “()[]{}”
输出:true
示例 3:
输入:s = “(]”
输出:false
示例 4:
输入:s = “([)]”
输出:false
示例 5:
输入:s = “{[]}”
输出:true
解题一:记录左括号,遇到右括号就找配对
我们以返回true的 “()[]{}” 和 “{[]}” 为例
我们以返回false的“([)]”为例
从上面这个分析图我们可以得到结论
1.我们需要从左到右遍历字符串
2.对于左括号我们需要把他们记录到容器中
3.遇到右括号时和容器中最后加入的左括号比较
配对成功则移除容器中最后加入的左括号,否则配对失败
4.如果字符长度是奇数压根儿就不用循环,直接是false,配对必须是偶数
解题一:记录左括号,遇到右括号就找配对
解题分析二:栈
解法二就是在解法一的基础上,将 List 换成 Stack栈
栈容器的特点:先进后出,后进先出
利用栈的特点,我们不需要专门去移除容器中的内容,只需要压栈弹栈即可
解题二:栈
总结
这道题的主要考点就是栈,当面对类似问题时,我们要根据不同数据结构类型容器的特点选择符合我们需求的容器来解决问题。
栈(Stack):先进后出
队列(Queue):先进先出
END