[Leetcode 20] 有效的括号

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
  1. 左括号必须用相同类型的右括号闭合。
  1. 左括号必须以正确的顺序闭合。
  1. 每个右括号都有一个对应的相同类型的左括号。
示例 1：
示例 2：
示例 3：
示例 4：
示例 5：
提示：
  • 1 <= s.length <= 10000
  • s 仅由括号 '()[]{}' 组成
 

解法：栈

  • 用一个栈保存尚未匹配的左括号；
  • 扫描字符：
    • 若是右括号，栈顶必须是对应的左括号，否则无效；匹配成功就弹栈；
    • 若是左括号，入栈；
  • 扫描结束栈空，则全部匹配成功。
      • notion image
复杂度
  • 时间：O(n)（每个字符入/出栈）
  • 空间：O(n)（栈）
上一篇
[Leetcode 19] 删除链表的倒数第 N 个节点
下一篇
[Leetcode 21] 合并两个有序链表

Relate Posts

[Leetcode 3] 无重复字符的最长子串

[Leetcode 14] 最长公共前缀

[Leetcode 32] 最长有效括号

[Leetcode 44] 通配符匹配

[Leetcode 171] Excel 列名转换为数字

[Leetcode 179] 最大数