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

爪哇缪斯

发布于 2023-09-06 13:40:51

1220

发布于 2023-09-06 13:40:51

文章被收录于专栏：爪哇缪斯

一、题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 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();
    }
}