20.有效的括号

题目

LeetCode 简单

题目

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

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

示例： 输入：s = "()"
输出：true

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

输入：s = "(]"
输出：false

题解

栈 O(n) O(n)

const s = '()()[}{}'

function isValid(s: string): boolean {
  const sLen = s.length
  if (sLen % 2 === 1) return false

  const sign = { '(': ')', '{': '}', '[': ']' }
  const stack = []
  for (let i = 0; i < sLen; i++) {
    const cur = s[i]
    const sCur = sign[cur]
    if (sCur) {
      //把对应的右符号推入栈
      stack.push(sCur)
    } else {
      //右符号
      const prev = stack.pop()
      if (prev === cur) {
        continue
      } else {
        return false
      }
    }
  }
  return stack.length === 0
}

console.log('🌰', isValid(s))