20. 有效的括号

1. 题目

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

有效字符串需满足：

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

示例 1：

1
2
输入：s = "()"
输出：true

示例 2：

1
2
输入：s = "()[]{}"
输出：true

示例 3：

1
2
输入：s = "(]"
输出：false

提示：

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

2. 思路

  • 已知题目仅由三种括号组成，同时要求每个右括号都有对应一个相同类型的左括号，且必须按照顺序闭合
  • 因此先初始化栈stack变量，用于收纳所有的左括号
  • 为了能够识别右括号对应的左括号，初始化mapping哈希表变量用于映射出对应的左-右括号
  • 遍历字符串s
    • 当遇到左括号时，将其收纳至栈中
    • 当遇到右括号时，如果栈为空，说明无法匹配，则直接返回false结果
    • 当遇到右括号时，如果栈不为空，则判断是否与栈顶字符形成匹配的括号对，如果不匹配，直接返回false结果
  • 完成遍历后则直接返回结果true

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public boolean isValid(String s) {
        var stack = new ArrayDeque<Character>();
        Map<Character, Character> mapping = Map.of(
            ')', '(',
            '}', '{',
            ']', '['
        );
        var arr = s.toCharArray();

        for (char ch : arr) {
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else if (!stack.isEmpty()) {
                var lastChar = stack.pop();
                if (mapping.get(ch) != lastChar) {
                    return false;
                }
            } else {
                return false;
            }
        }

        return stack.isEmpty();
    }
}

4. 复杂度

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

image-20230907180930337