数组与字符串之有效的括号

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

有效字符串需满足:

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

示例

输入: "()"
输出: true

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

输入: "(]"
输出: false

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

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

分析

可以使用, 遇到左括号推入栈中, 遇到右括号时, 从栈顶取出元素进行匹配, 如果不匹配则返回false, 否则继续匹配

代码

Python3

def isValid(self, s):
  dic = {
    '(': ')',
    '{': '}',
    '[': ']',
    '?': '?'
  }
  stack = ['?']

  for item in s:
    if item in dic:
      # 如果item位左括号则入栈
      stack.append(item)
    # 否则通过哈希表判断括号对应关系, 如果出栈的括号与当前遍历的item不对应则返回# false
    elif dic[stack.pop()] != item:
      return False
  return len(stack) == 1

JavaScript

function isValid(s) {
  let arr = []
  let len = s.length
  if (len % 2) return false

  for (let i = 0; i < len; i++) {
    let temp = s[i]
    switch (temp) {
      case '(':
        arr.push(temp)
        break
      case '{':
        arr.push(temp)
        break
      case '[':
        arr.push(temp)
        break
      case ')':
        if (arr.pop() !== '(') return false
        break
      case '}':
        if (arr.pop() !== '{') return false
        break
      case ']':
        if (arr.pop() !== '[') return false
        break
    }
  }
  return !arr.length
}

提示

stack为空时, stack.pop()会出错, 因此此处给stack赋初始值’?’并在哈希表中添加’?’:’?’予以配合, 此时当stack为空且item为右括号时可以正常提前返回false.

s以左括号结尾时, 此情况下可以正常遍历完s, 但stack中会遗留未出栈的左括号, 因此最后需返回len(stack) == 1以判断是否是有效的括号组合