LeetCode-20 有效的括号

作者: 编程半岛 | 来源:发表于2019-06-04 12:09 被阅读0次
    • 题目:20. 有效的括号
    • 难度:简单
    • 分类:栈
    • 解决方案:入栈出栈

    今天我们学习第20题有效的括号,这是一道关于栈的简单题,对熟悉栈的基本使用很有帮助。下面我们看看这道题的题目描述。

    题目描述

    给定一个只包括 (){}[] 的字符串,判断字符串是否有效。

    有效字符串需满足:

    • 左括号必须用相同类型的右括号闭合。
    • 左括号必须以正确的顺序闭合。

    注意空字符串可被认为是有效字符串。

    示例 1:

    输入: "()"
    输出: true
    

    示例 2:

    输入: "()[]{}"
    输出: true
    

    示例 3:

    输入: "(]"
    输出: false
    

    示例 4:

    输入: "([)]"
    输出: false
    

    示例 5:

    输入: "{[]}"
    输出: true
    

    分析

    这个题是目前为止遇到的第一个相关题目,对于栈不太熟悉的小伙伴可以扫描文章下方的二维码,关注『 算法半岛』回复『 数据结构目录』,即可获得相关学习资料。

    对于这个题,我们借助一个栈,遍历字符串时,当遇到({[时,将字符入栈;当遇到)}]时,判断栈顶是否为其对应的左括号,如果对应得上,弹出栈顶元素,如果栈顶为空或则对应不上,则返回false。对示例5的详细示意图如下所示:

    示例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;
            
        }
    }
    
    提交结果

    Github地址

    LeetCode-20 有效的括号

    参考链接

    有效的括号

    更多文章,请扫描二维码关注『算法半岛』

    相关文章

      网友评论

        本文标题:LeetCode-20 有效的括号

        本文链接:https://www.haomeiwen.com/subject/oselxctx.html