九旬的博客

描述

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

总结

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