有效的括号

发表于 | 分类于 |
字数统计: 356 字 | 阅读时长 ≈ 1 分钟

题目描述：给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

示例 1：
输入：s = “()”
输出：true

示例 2：
输入：s = “()[]{}”
输出：true

示例 3：
输入：s = “(]”
输出：false

示例 4：
输入：s = “([)]”
输出：false

示例 5：
输入：s = “{[]}”
输出：true

方法一：栈

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
27
28
29
30
31
32
33
34
class Solution {
  public boolean isValid(String s) {
    int n = s.length();
    if (n % 2 == 1) {
      return false;
    }
    Stack<Character> stack = new  Stack<>();
    for(char c: s.toCharArray()) {
      if(c == '(') stack.push(')');
      else if(c == '[') stack.push(']');
      else if(c == '{') stack.push('}');
      else if(stack.isEmpty() || c!= stack.pop()) return false;
    }
    return stack.isEmpty();
  }
}

var isValid = function(s) {
  let len = s.length
  if(len % 2 === 1) return false
  let stack = []
  for(let c of s) {
    if(c === '(') {
      stack.push(')')
    } else if (c === '[') {
      stack.push(']')
    } else if (c === '{') {
      stack.push('}')
    } else if (!stack.length || c !== stack.pop()) {
      return false
    }
  }
  return stack.length === 0
};
  • 复杂度分析
    • 时间复杂度 O(N)：正确的括号组合需要遍历 1 遍 s；
    • 空间复杂度 O(N)：栈使用线性的空间大小。

执行结果：通过

  • 执行用时：1 ms, 在所有 Java 提交中击败了99.28%的用户

  • 内存消耗：36.3 MB, 在所有 Java 提交中击败了93.49%的用户