↑点击上面"算法半岛"
关注"算法半岛"第一时间接收最新文章
> 题目: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;
}}
LeetCode-20 有效的括号:https://github.com/JacobLei/leetcode/blob/master/src/main/java/A20_ValidParentheses.java)
有效的括号:https://leetcode-cn.com/problems/valid-parentheses/