0. 序言
"有效的括号"这一题，可以帮助我们更好的理解栈这个数据结构。
1. 题目描述
给定一个只包括'('，')’，'{'，'}'，'['，']'的字符串，判断字符串是否有效。
有效字符串需满足：
① 左括号必须用相同类型的右括号闭合。
② 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例1：
输入: "( )"
输出: true
示例2：
输入: "( )[ ]{ }"
输出: true
示例3：
输入: "( ]"
输出: false
示例4：
输入: "( [ ) ]"
输出: false
示例5：
输入: "{ ( ) }"
输出: true
2. 解决方案
- 分析
① 字符串元素是偶数个，否则无效，注意0也是偶数。
② 括号之间必须是相互对应的关系。
③ 除去相互匹配的左右括号之外，不能有任何其他元素。
④ 空字符串是一个有效字符串，意味着，空字符串的时候这个字符串有效，即公式返回true。 - 思路
① 判断字符串元素的个数是否为偶数，不为偶数个返回false
② 创建一个栈，用来存放左括号。
③ 判断字符串中的元素是否是右括号，如果是右括号，就看看此时栈顶的左括号是否相互匹配，如果不匹配返回false，如果匹配就把栈顶的元素弹栈，然后再看字符串的下一个元素是否和栈顶的元素相匹配，如果不匹配返回false，循环往复。
④ 判断栈是否为空，为空意味着字符串是有效字符串，如果不为空，意味着字符串中的左右括号并非一一对应的关系。 - 代码
import java.util.Stack;
class Solution {
public boolean isValid(String s) {
int length = s.length();
if (length%2!=0)
return false;
Stack<Character> stack = new Stack<>();
for (int i = 0; i <s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
}else{
if (stack.isEmpty())
return false;
char topChar = stack.pop();
if (c ==')' && topChar !='('){
return false;
}else if (c =='}' &&topChar !='{'){
return false;
}else if (c ==']' && topChar !='['){
return false;
}
}
}
return stack.isEmpty();
}
}
当然我们也可以把Stack，换为我们自定义的ArrayStack。
3. 复杂度分析
- 时间复杂度分析
① 当字符串个数为奇数的时候，时间复杂度为O(1)，这是最好情况时间复杂度。
② 当字符串个数为偶数的时候，时间复杂度为O(n)，这是最坏情况时间复杂度。
③ 字符串为奇数或偶数的概率，各为1/2,所以1×1/2 + n×1/2 = (n+1)/2，所以加权平均时间复杂度为O(n)
④ 这个示例并适合用均摊时间复杂度分析。因为字符串是奇数或者偶数，两者并没有前后关系，对均摊复杂度不了解的，可以跳转阅读：//www.greatytc.com/p/59f380c6ffcd
综上：这段代码的时间复杂度为O(n). - 空间复杂度分析
涉及多个开括号入栈，所以空间复杂度为O(n)
4. 后续
如果大家喜欢这篇文章，欢迎点赞！
如果想看更多 数据结构 方面的文章，欢迎关注!
