zhangdizhangdi

20. 有效的括号 🟩

题目

LeetCode 简单

题目

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

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

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

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

示例3：
输入：s = “(]”
输出：false

提示：s 仅由括号 ‘()[]{}’ 组成

题解

栈

  • 时间复杂度：O(n)

    其中 n 是字符串 s 的长度。

  • 空间复杂度：O(n+∣Σ∣)

    其中 Σ 表示字符集，本题中字符串只包含 6 种括号，∣Σ∣=6。栈中的字符数量为 O(n)，而哈希表使用的空间为 O(∣Σ∣)，相加即可得到总空间复杂度。

js 
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('------')
    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
}

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