zhangdizhangdi

20.有效的括号

题目

LeetCode 简单

题目

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

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

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

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

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

题解

栈 O(n) O(n)

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

function isValid(s) {
  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]

    console.log('当前符号', cur, '当前对应右符号', sCur)

    if (sCur) {
      //把对应的右符号推入栈
      stack.push(sCur)

      console.log('stack', stack.toString())
    } else {
      //右符号
      const prev = stack.pop()
      if (prev === cur) {
        continue
      } else {
        return false
      }
    }
  }
  return stack.length === 0
}

console.log('🌰', isValid(s))
执行结果
当前符号 ( 当前对应右符号 )
stack )
当前符号 ) 当前对应右符号 undefined
当前符号 ( 当前对应右符号 )
stack )
当前符号 ) 当前对应右符号 undefined
当前符号 [ 当前对应右符号 ]
stack ]
当前符号 } 当前对应右符号 undefined
🌰 false