萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣第20题-有效的括号

发表于 2022-04-12 | 分类于 力扣刷题 | 0 | 阅读次数 136

题目描述

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

有效字符串需满足:

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

题目链接

样例

示例 1:
输入:s = "()"
输出:true

示例 2:
输入:s = "()[]{}"
输出:true

示例 3:
输入:s = "(]"
输出:false

示例 4:
输入:s = "([)]"
输出:false

示例 5:
输入:s = "{[]}"
输出:true

提示:
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

题目评估

官方难度:简单
知识点:栈、字符串

分析

使用栈来解题:从左到右捋字符串,左括号就压栈,右括号就和栈顶括号匹配,如果匹配成功,就弹栈,匹配不成功就直接返回失败。

Java代码题解

class Solution {
    public boolean isValid(String s) {
        int len = s.length();
        // 如果括号个数为奇数个直接返回false
        if (len % 2 == 1) {
            return false;
        }
        LinkedList<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            Character current = s.charAt(i);
            // 当前括号为左括号
            if (getRightBracket(current) != null) {
                // 把左括号压栈
                stack.addFirst(current);
            }
            // 当前括号为右括号
            else {
                Character top = stack.peek();
                // 如果栈空直接返回false
                if (top == null) {
                    return false;
                }
                // 把当前右括号和栈顶括号匹配
                if (current == getRightBracket(top)) {
                    stack.poll();
                } else {
                    return false;
                }
            }
        }
        if (stack.isEmpty()) {
            return true;
        } else
            return false;
    }

    private Character getRightBracket(char left) {
        switch (left) {
            case '(':
                return ')';
            case '[':
                return ']';
            case '{':
                return '}';
            default:
                return null;
        }
    }
}

复杂度分析

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

(借鉴自官方题解)

# 算法 # 程序设计 # 力扣
力扣第18题-四数之和
力扣第21题-合并两个有序链表
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

77 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持