20.有效的括号.md

LeetCode-20 有效的括号

难度：简单

类型：栈

题目：

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

示例 1:

输入: "()" 输出: true

示例 2:

输入: "()[]{}" 输出: true

示例 3:

输入: "(]" 输出: false

示例 4:

输入: "([)]" 输出: false

示例 5:

输入: "{[]}" 输出: true

思路：

遍历字符的过程中，遇到左括号就将左括号对应的右括号推入到栈中，然后遇到右括号，就取出栈顶的括号，判断两个括号是否相等。正常情况下，左括号是与栈顶的括号相等的，如果相等，则将括号出栈，继续遍历字符。如果不相等，直接返回false,说明不符合题目的要求。

最终遍历完后，栈应该为空。

实现：

JavaScript:

/**
* @param  {string} s
* @return {boolean} 
*/
// 将左括号与右括号形成映射关系
var map = {
  "(": ")",
  "[": "]",
  "{": "}"
}

function isValid (s) {
  if (!s) return true
  let len = s.length 
  let stack = []
  for (let i = 0; i < len; i++) {
    let ch = s[i]
    // 遇到左括号就将左括号对应的右括号推入栈中
    if (ch === '(' ||  ch === '[' || ch === '{') {
      stack.push(map(ch))
    } else {
      // 如果stack为空或者 ch !== 栈顶取出的括号 直接返回false 
      if (!stack.length || ch !== stack.pop()) {
        return false
      }
    }
  }
  return !stack.length
}