1. 有效的括号（20）

力扣题目链接

一、题目内容 简单

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

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例1：

输入：s = “()” 输出：true

示例2：

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

示例3：

输入：s = “(]” 输出：false

二、解题思路

按照自然的解题方式，我们需要一个符号一个符号地检查，如果是左边括号，我们先放着。
当遇到右边括号，我们会往字符串 s 左边去查找最近的括号，如果是相应的左括号，那么把这一对括号去掉。
接着继续按着字符串 s 往右边找，依次类推，直到 s 遍历结束

那么我们用一个栈来存放，我们查到的左边括号。

1. 当遇到右边括号时，从栈顶取出符号，即往字符串 s 左边去查找最近的括号
   1. 如果是相应的左括号，那么把该括号从栈顶删除。
   2. 如果不是相应的左括号，那么说明字符串的括号是无效的，直接返回 false
2. 接着继续按着字符串 s 往右边找，依次类推，直到 s 遍历结束。
3. 判断栈是否为空，空返回 true，非空返回 false

另外，由于括号都是对称的，那么我们可以在一开始先判断字符串是否为偶数，如果不是偶数，说明不是有效的括号。

三、具体代码

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  // 方法一：栈Stack + 暴力判断
  if (s.length % 2 === 1) return false;
  const stack = [];
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '('
      || s[i] === '['
      || s[i] === '{'
    ) {
      stack.push(s[i]);
    } else {
      const c = stack[stack.length - 1];
      if (c === '(' && s[i] === ')'
        || c === '[' && s[i] === ']'
        || c === '{' && s[i] === '}'
      ) {
        stack.pop();
      } else { 
        return false
      }
    }
  }
  return stack.length === 0;
};

四、其他解法

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  // 方法二：用栈 Stack + 字典 Map 优化
  if (s.length % 2 === 1) return false;
  const stack = [];
  const map = new Map([
    ['(', ')'],
    ['[', ']'],
    ['{', '}'],
  ])
  for (let i = 0; i < s.length; i++) {
    if (map.has(s[i])) stack.push(s[i])
    else {
      const c = stack[stack.length - 1];
      if (!(map.get(c) === s[i])) return false;
      stack.pop();
    }
  }
  return stack.length === 0;
  /**
   * 时间复杂度O(n)
   * 空间复杂度O(1)
   */
};