有效的括号.md

有效的括号

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

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

示例：

输入: "()"
输出: true

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

输入: "(]"
输出: false

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

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

压栈解法

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  if (!s || !s.length) return true
  const stack = []
  const optionsMap = {
    '(': ')',
    '{': '}',
    '[': ']',
  }
  for (let i = 0; i < s.length; i++) {
    // 左边的括号进栈
    if (optionsMap[s[i]]) {
      stack.push(s[i])
    } else if (s[i] === ''){
      continue
    } else {
      // 提取把最后一个元素进行匹配判断
      const last = stack.pop()
      if (optionsMap[last] !== s[i]) {
        return false
      }
    }
  }
  return stack.length === 0
};

字符串替换解法

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  while (/(\{\})|(\[\])|(\(\))/.test(s)) {
    s = s.replace(/(\{\})|(\[\])|(\(\))/, '')
  }
  return s === ''
};