大家好,我是程序员吴师兄,今天跟大家分享一道和 栈 有关的题目,超级简单也超级容易理解,这道题目曾经出现在 bilibili 的面试中。
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
示例 1:
输入:s = "()"
输出:true
示例 2:
输入:s = "([)]"
输出:false
提示:
我们用 四步分析法 来分析一下这道题目。
1.模拟
有效的情况:
1)不嵌套
2)嵌套
无效的情况:
1)长度为奇数,左括号多余
2)长度为奇数,右括号多余
3)长度为偶数,左括号与右括号不配对
4)长度为偶数,部分子表达式可以配对,但外部不配对
2.规律
通过上述的模拟,可以总结出以下 3 个特点:
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)。最坏情况下,栈的大小将是输入字符串的长度。
1、https://leetcode-cn.com/problems/valid-parentheses/solution/valid-parentheses-fu-zhu-zhan-fa-by-jin407891080/
2、https://t10.lagounews.com/aR44RbR+c190C