描述

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

有效字符串需满足:

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

输入:s = "([)]"
输出:false
1
2

示例 5:

输入:s = "{[]}"
输出:true
1
2

题目:有效的括号open in new window

解法

利用栈先进后出的特性,依次左储存括号,每当遇到右括号时,就去匹配响应的左括号,匹配成功则出栈,最后栈为空则表示匹配正确。

let isValid = function(s) {
  let strArr = s.split("");
  let len = s.length;
  let flagArr = {
    "(": ")",
    "{": "}",
    "[": "]",
  };
  let stack = []; // 存放临时括号
  for (let i = 0; i < len; i++) {
    let left = strArr[i];
    if (flagArr.hasOwnProperty(left)) {
      stack.push(left);
    } else {
      if (strArr[i] !== flagArr[stack.pop()]) {
        return false;
      }
    }
  }
  return stack.length == 0;
};

let res = isValid("()[]");
console.log(res); // 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

思路:

  1. 使用 split 将传入的字符串转为数组,拿到长度,并建立一个左右括号的映射。
  2. 建立 stack 空栈,用于储蓄括号。
  3. for 这个数组
    1. 判断出现左括号时,将当前左括号入栈。
    2. 判断非左括号(也就是右括号时),将最后入栈的左括号拿来比对是否匹配
      1. 匹配则出栈,然后继续 for
      2. 不匹配就 return false
    3. for 结束后,判断栈为空,就 return true

复杂度分析

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

总结

用到了栈的一些特性,用数组模拟栈先入后出的原则。然后通过匹配得出结果。

上次更新: 11/1/2023, 3:16:38 AM
Contributors: zhangningle