图解LeetCode——20. 有效的括号

一、题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 每个右括号都有一个对应的相同类型的左括号。

二、示例

2.1> 示例 1：

【输入】s = "()"
【输出】true

2.2> 示例 2：

【输入】s = "()[]{}"
【输出】true

2.3> 示例 3：

【输入】s = "(]"
【输出】false

提示：

• 1 <= s.length <= 10^4
• s 仅由括号 '()[]{}' 组成

三、解题思路

根据题目描述，我们需要校验给定的字符串s是否是有效字符串，这里的“有效”就是通过是否是完整括号来决定的（小括号、中括号、大括号）。那么，对于这种字符“配对”的题目，我们就很容易能够想到，可以采用堆栈的方式进行解题。那么此处，我们可以采用Stack类来提供堆栈能力的支持，也可以使用双向队列Deque来提供堆栈能力的支持，由于在LeetCode的执行效率中，Deque的执行效率是要比Stack高的，所以我建议大家采用Deque来模拟堆栈行为。

基本的解题思想确定了之后，我们就可以通过遍历字符串 + 堆栈来进行解题了。假设我们将遍历到字符串s的字符称为c，那么此处入栈我们指定了3个约束条件：

【条件1】如果遍历的字符c等于'('，那么我们就将字符‘)’执行入栈操作；
【条件2】如果遍历的字符c等于'['，那么我们就将字符‘]’执行入栈操作；
【条件3】如果遍历的字符c等于'{'，那么我们就将字符‘}’执行入栈操作；

那么，针对不满足以上3个条件，我们只需要执行如下判断：

【判断1】将stack栈顶元素弹出，如果它等于c，则继续执行；
【判断2】将stack栈顶元素弹出，如果它不等于c，则终止执行，返回false；

好了，以上就是本题的解题思路了，为了方便大家理解，我们以输入s = "()[){}"为例，看一下其具体的执行过程是怎么样的。具体详情，请见下图所示：

四、代码实现

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') stack.addLast(')');
            else if (c == '[') stack.addLast(']');
            else if (c == '{') stack.addLast('}');
            else if (stack.isEmpty() || c != stack.removeLast()) return false;
        }
        return stack.isEmpty();
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o)/ ~ 「干货分享，每天更新」