• 题目：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 有效的括号

参考链接

有效的括号

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