- 题目:20. 有效的括号
- 难度:简单
- 分类:栈
- 解决方案:入栈出栈
今天我们学习第20题有效的括号,这是一道关于栈的简单题,对熟悉栈的基本使用很有帮助。下面我们看看这道题的题目描述。
题目描述
给定一个只包括 (
,)
,{
,}
,[
,]
的字符串,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
分析
这个题是目前为止遇到的第一个栈相关题目,对于栈不太熟悉的小伙伴可以扫描文章下方的二维码,关注『 算法半岛』回复『 数据结构目录』,即可获得相关学习资料。
对于这个题,我们借助一个栈,遍历字符串时,当遇到(
、{
或[
时,将字符入栈;当遇到)
、}
或]
时,判断栈顶是否为其对应的左括号,如果对应得上,弹出栈顶元素,如果栈顶为空或则对应不上,则返回false
。对示例5的详细示意图如下所示:
上述分析所对应的java
代码如下所示:
class Solution {
public boolean isValid(String s) {
// 申请栈
Stack<Character> stack = new Stack<>();
// 将字符串转化为字符数组
char[] chars = s.toCharArray();
for (int i=0; i<chars.length; i++){
// 判断当前字符是否为 '(' 、'[' 或 '{'
if (chars[i] == '(' || chars[i] == '[' || chars[i] == '{'){
// 如果时,则入栈
stack.push(chars[i]);
}else{
// 如果不是,则为')'、']'或'}'',判断栈中是否有对应的左括号
if (stack.empty()){
return false;
}else{
char c = stack.pop();
if ((chars[i] == ')' && c != '(') || (chars[i] == ']' && c != '[') || (chars[i] == '}' && c != '{')){
return false;
}
}
}
}
// 只有当栈为空时,才为true
return stack.empty() ? true : false;
}
}
提交结果
网友评论