大家好，我是程序员吴师兄，今天跟大家分享一道和 栈
一、题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "([)]"
输出：false
提示：
- 1 <= s.length <= 104
- s 仅由括号 '()[]{}' 组成
二、题目解析
我们用 四步分析法
- 模拟：模拟题目的运行。
- 规律：尝试总结出题目的一般规律和特点。
- 匹配：找到符合这些特点的数据结构与算法。
- 边界：考虑特殊情况。
1.模拟
有效的情况：
1）不嵌套
2）嵌套
无效的情况：
1）长度为奇数，左括号多余
2）长度为奇数，右括号多余
3）长度为偶数，左括号与右括号不配对
4）长度为偶数，部分子表达式可以配对，但外部不配对
2.规律
通过上述的模拟，可以总结出以下 3 个特点：
- 1、(与）、[与]、{与}是一一对应的关系，无法配对是无效的
- 2、对于有效的括号，它的部分子表达式仍然是有效的括号，比如{ [ ( ) ]}
- 3、部分子表达式如果建立了配对关系，是有效的括号，那么消除
- 4、奇数长度的字符串总是无效的。
3.匹配
整个过程分为两步，一个是配对，一个是消除。
配对 过程，（ 与 ）、[ 与 ]、{ 与 }。
消除 的过程是由内向外进行，先判断能否消除部分子表达式（内），再判断能否消除整体表达式（外），但在遍历的过程却是由外向内进行遍历，需要保存状态，栈
4.边界
所谓边界，即特殊情况：
- 字符串的长度为奇数
三、动画图解
四、参考代码
// 登录 https://www.algomooc.com 查看更多图解
class Solution {
public boolean isValid(String s) {
// 当字符串长度为奇数的时候，属于无效情况
// 条件说明了长度至少为 1，所以不需要在判空
if (s.length() % 2 == 1) {
return false;
}
//构建栈
Stack<Character> stack = new Stack<Character>();
//由外向内遍历字符串
for(char c : s.toCharArray()){
if(c == '('){
stack.push(')');
}else if(c == '['){
stack.push(']');
}else if( c == '{'){
stack.push('}');
}else if( stack.isEmpty() || c != stack.pop()){
//表明有多余的括号
return false;
}
}
return stack.isEmpty();
}
}
五、复杂度分析
时间复杂度
时间复杂度为 O(N)。需要遍历一遍字符串。
空间复杂度
空间复杂度 O(N)。哈希表和栈使用线性的空间大小，最坏情况下，栈的大小将是输入字符串的长度。
六、参考引用