当前位置: 首页 > backend >正文

力扣(有效括号)

LeetCode 20. 有效的括号:解析与不匹配案例全解

一、题目分析

在这里插入图片描述

有效的括号字符串需同时满足三个条件:

  • 左括号必须用相同类型的右括号闭合
  • 左括号必须以正确的顺序闭合
  • 每个右括号都有对应的左括号

我们需要判断一个仅包含()[]{}的字符串是否满足这些条件。

二、算法核心思路:栈的巧妙运用

栈的"后进先出"特性与括号匹配的"最近原则"高度契合,算法核心思路如下:

  1. 遍历字符串:逐个处理每个括号字符
  2. 左括号处理:遇到左括号时,将其对应的右括号压入栈中
    • ( 对应 ) 入栈
    • [ 对应 ] 入栈
    • { 对应 } 入栈
  3. 右括号处理:遇到右括号时,检查栈顶元素
    • 若栈为空或栈顶元素与当前右括号不匹配,说明字符串无效
    • 若匹配,则弹出栈顶元素,继续遍历
  4. 最终判断:遍历结束后,栈为空则字符串有效,否则无效

三、所有不匹配情况及算法处理

1. 字符串长度为奇数

案例"(()""[]}""{"

原理:有效的括号必须成对出现,总长度必然为偶数。长度为奇数时,至少有一个括号无法匹配。

算法处理

if (s.length() % 2 != 0) { return false;
}

代码开头即进行此判断,提前终止,提高效率。

2. 右括号无对应左括号

案例")()""[]))"")]"

原理:遍历到右括号时,栈为空(没有对应的左括号入栈),说明该右括号多余。

算法处理

// 右括号:检查栈空或不匹配
if (stack.empty() || letter != stack.peek()) { return false;
}

如处理")()"时,第一个字符是')',此时栈为空,直接返回false

3. 括号类型不匹配

案例"([)]""{[)]}""(]"

原理:右括号与最近的左括号类型不匹配,违反"相同类型闭合"原则。

算法处理
通过比较当前右括号与栈顶元素(预期的右括号)判断是否匹配。

"{[)]}"为例:

  • 处理'{',栈顶为'}'
  • 处理'[',栈顶为']'
  • 处理')',栈顶是']'')' != ']',判定不匹配

4. 左括号未被完全匹配

案例"(()""{{[}""([{"

原理:存在未被右括号匹配的左括号,遍历结束后栈中仍有剩余元素。

算法处理

// 栈空则所有左括号匹配完成
return stack.empty();

"(()"为例:

  • 处理'(',栈顶为')'
  • 处理'(',栈顶为')'
  • 处理')',弹出栈顶,栈中仍剩一个')'
  • 遍历结束后栈非空,返回false

四、完整代码实现

class Solution {public boolean isValid(String s) {// 长度为奇数,直接无效if (s.length() % 2 != 0) { return false;}int len = 0;Stack<Character> stack = new Stack<>();while (len < s.length()) {char letter = s.charAt(len);// 左括号:压入对应右括号if (letter == '(') { stack.push(')');} else if (letter == '[') {stack.push(']');} else if (letter == '{') {stack.push('}');} else { // 右括号:检查栈空或不匹配if (stack.empty() || letter != stack.peek()) { return false;}// 匹配则弹出栈顶stack.pop(); }len++;}// 栈空则所有左括号匹配完成return stack.empty(); }
}

五、算法复杂度分析

  • 时间复杂度:O(n),其中n是字符串长度。每个字符最多入栈和出栈各一次,均为O(1)操作
  • 空间复杂度:O(n),最坏情况下(全为左括号),栈需要存储n/2个字符

有效的括号判断算法巧妙利用了栈的"后进先出"特性,通过将左括号转换为对应右括号入栈,将匹配问题转化为简单的相等判断。算法能够处理所有可能的不匹配情况:

  • 长度为奇数的字符串
  • 右括号无对应左括号
  • 括号类型不匹配
  • 左括号未被完全匹配
http://www.xdnf.cn/news/18727.html

相关文章:

  • 用蒙特卡洛法求解三门问题和Π
  • GPIO子系统自主实现(简单版)
  • 开发避坑指南(36):Java字符串Base64编码实战指南
  • 迭代器设计模式
  • 《XXL-Job 全面介绍:Java 开发中的分布式任务调度框架》
  • 【互动屏幕】为什么现在数字展厅偏爱地面互动装置?
  • 嵌入式Linux内核编译与配置
  • 神经网络与梯度算法:深度学习的底层逻辑与实战解析
  • 微论-神经网络中记忆的演变
  • “Datawhale AI夏令营--coze空间
  • Java 探针的原理
  • 深入解析:为什么应该避免使用 atoi、atol 和 atof 函数
  • 《C++ Primer 第五版》省略符号(...)
  • 【小增长电商技术分享】电商支付宝批量转账工具技术测评:架构特性、合规风险与选型方法论,支付宝官方|小增长|云方付|易推客省心返
  • vi/vim 查找字符串
  • Ajax笔记(上)
  • Spark面试题
  • Redis面试精讲 Day 30:Redis面试真题解析与答题技巧
  • 南京魔数团:AR技术引领远程协作新纪元
  • Java网络编程:从入门到精通
  • STM32之DMA详解
  • 算法题记录01:
  • 8月25日
  • 专题:2025人工智能2.0智能体驱动ERP、生成式AI经济现状落地报告|附400+份报告PDF、原数据表汇总下载
  • [论文阅读]RQ-RAG: Learning to Refine Queries for Retrieval Augmented Generation
  • k8s的etcd备份脚本
  • AR技术赋能农业机械智能运维
  • 电机控制::基于编码器的速度计算与滤波::RLS
  • 【C++】第二十六节—C++11(中) | 右值引用和移动语义(续集)+lambda
  • Linux_用 `ps` 按进程名过滤线程,以及用 `pkill` 按进程名安全杀进程