2022-06-01.md

每日一题 - 有效的括号

信息卡片

• 时间：2022-06-01
• 题目链接：https://leetcode.com/problems/valid-parentheses/
• tag：栈 字符串

题目描述

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

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

示例1：

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

示例2：

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

示例3：

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

示例4：

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

示例5：

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

提示：

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

进阶：

思路分析

1. 每当遇到一个 右括号（不论小、中、大），前面必须有一个匹配的 左括号
2. 遍历，遇到 右括号，按顺序往前回溯对应有没有，可以想到：先进后出 - 栈
3. 遍历数据依次入栈，遇到 右括号 时栈顶出栈进行匹配 → 1

LeetCode 394 类似

参考答案

1. 利用栈 $O(n)$

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

function isValid(s) {
  // 如果长度不是偶数则肯定不符合
  if (s.length % 2 === 1) {
    return false
  }
  let stack = []
  for (let c of s) {
    if (c === '(') stack.push(')')
    else if (c === '{') stack.push('}')
    else if (c === '[') stack.push(']')
    // 不是左括号就栈顶出栈，判定是否相等（前面入栈的为匹配括号）
    else if (stack.length === 0 || stack.pop() !== c) return false
  }
  return !stack.length
}