Freeisms

# 有效的括号

力扣🔗：https://leetcode-cn.com/problems/valid-parentheses (opens new window)

# 题目

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

有效字符串需满足：

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

提示：

  • 1 <= s.length <= 10^4
  • s 仅由括号 '()[]{}' 组成

# 解题思路

  • 模拟栈后进先出操作，进行括号匹配。
  • 创建数组 arr，用来存放没有匹配的括号字符。
  • 依次遍历 s 中的每个字符，判断该字符是否是右括号（)、}、]），如果是则判断 arr 中栈顶元素是否与该字符匹配，若匹配则弹出该元素，否则推入当前遍历到的字符。
  • 最后判断 arr 数组是否是空数组，如果是则表示该字符串有效。

# 代码实现

/**
 * @param {string} s
 * @return {boolean}
 */
function isValid(s) {
  if (s.length % 2) return false // 如果长度为奇数
  const arr = []
  
  for (let i = 0; i < s.length; i++) {
    const c = s[i]
    const p = c === ')' ? '(' : c === '}' ? '{' : c === ']' ? '[' : false
    p && p === arr[arr.length - 1] ? arr.pop() : arr.push(c)
  }

  return arr.length === 0
}

← 合并两个有序链表 →