数据结构与算法►力扣

20.有效的括号

题目描述

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

有效字符串需满足：

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

题解

该题是栈这种数据结构的典型使用场景，栈的特点是后进先出。

栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isValid(String s) {
        var n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        var pairs = Map.of(')', '(', ']', '[', '}', '{');
        var stack = new LinkedList<Character>(); 
        for (i = 0; i < n; i++) {
            var ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || !Objects.equals(stack.peek(), pairs.get(ch))) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

提交到力扣：

提交结果